Submit solution
Points:
0.46 (partial)
Time limit:
0.38s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem type
Allowed languages
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
Comments
Em đề xuất thêm tag quy hoạch động cho bài này ạ