Gửi bài giải
Điểm:
0,46 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho 2 số ~n~ và ~k~ ~\left( 2 \le k \le n \le 10^6\right)~
Hãy đếm xem có bao nhiêu xâu nhị phân độ dài ~n~ mà không có quá ~k~ số ~0~ hoặc ~k~ số ~1~ nào liên tiếp nhau.
Input
Gồm ~1~ dòng duy nhất là ~2~ số ~n~ và ~k~.
Output
Gồm ~1~ dòng duy nhất là số dãy nhị phân thoả mãn (~module~ ~10^9~).
Sample Input
3 2
Sample Output
6
Bình luận
Em đề xuất thêm tag quy hoạch động cho bài này ạ