Nhảy cầu thang
Đề bài
Mô tả
Misdeed đang nghĩ đến chuyện nhảy. Nhảy xuống cầu thang.
Cầu thang của Misdeed có bậc và anh ấy đang đứng ở bậc . Anh ấy định nhảy tổng cộng lần, mỗi lần có thể nhảy xuống bao nhiêu bậc cũng được (kể cả không nhảy bậc nào), miễn là không vượt quá chân cầu thang, tức là không đáp xuống thấp hơn bậc . Hãy đếm giúp Misdeed số cách nhảy thành công.
Đó là đề bài lúc đầu. Tuy nhiên, Misdeed vừa xấu tính vừa khó chịu.
Gọi dãy các lần nhảy là (các số nguyên không âm). Bây giờ, ở lượt thứ , Misdeed sẽ nhảy bậc. Do đó . Ngoài ra, phải có (với là phép AND theo bit); nếu không, Misdeed sẽ trượt chân và đập đầu vào mép bậc thang.
Yêu cầu: Đếm số dãy thỏa mãn cả hai điều kiện trên, lấy phần dư khi chia cho .
Dữ liệu vào
Một dòng gồm ba số nguyên , , : số bậc của cầu thang, số lần nhảy và giá trị AND yêu cầu.
Dữ liệu ra
In ra số dãy thỏa mãn, lấy phần dư khi chia cho .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 11 3 1 | 4 | Các dãy thỏa mãn là , , , . |
| 10 2 0 | 26 | Ví dụ bổ sung. Cần và ; chẳng hạn cho dãy (). |
Bình luận