Đếm xâu con không quá K kí tự 0 hoặc K kí tự 1
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
SDP2004C.INP
Output:
SDP2004C.OUT
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Xâu nhị phân là xâu chỉ gồm các kí tự "0" hoặc "1".
Cho hai số nguyên dương ~K~ và ~N~ (~K≤N~).
Yêu cầu:
Đếm số lượng 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:
Cho từ tệp SDP2004C.INP
Gồm một dòng duy nhất chứa hai số nguyên dương ~N~ và ~K~ (~2≤K≤N≤10^6~ ).
Output:
In ra kết quả bài toán sau khi chia lấy dư cho ~10^9~.
Ví dụ:
SDP2004C.INP
3 2
SDP2004C.OUT
6
Bình luận