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
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Đề xuất thêm tag nhân ma trận
Em đề xuất thêm tag quy hoạch động cho bài này ạ