| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P192PROE - Problem E - Bài toán những viên đá |
Một ngày đẹp trời, Oppa đang trên đường đến tới trường thì gặp Unnie - crush bấy lâu nay. Sau một hồi lân la hỏi chuyện thì Oppa biết được crush của mình đang gặp rắc rối với một bài toán ở contest gần đây. Oppa muốn làm Unnie vui nhưng không biết phải làm sao nên đành nhờ các bạn.
Bài toán như sau:
Unnie có hai loại đá quý là đá thường và đá ma thuật. Với một viên đá ma thuật có thể tách thành m viên đá thường. Unnie có một khay chứa với n ô trống, mỗi viên đá sẽ chiếm 1 ô. Unnie ban đầu chọn 1 số viên đá ma thuật và bắt đầu tách một số trong số chúng. Một viên đá ma thuật nếu bị tách ra sẽ chiếm m ô. Ví dụ ban đầu có 3 viên đá ma thuật kí hiệu là 111, sau khi tách viên thứ 2 thành m viên thường(Kí hiệu là 0) với m = 2 thì sẽ được 1001. Hỏi có bao nhiêu trạng thái có thể của n ô trống.
Hai trạng thái là khác nhau nếu số lượng đá ma thuật ban đầu lấy khác nhau hoặc chỉ số các viên đá được tách ra khác nhau.
Input
Một dòng duy nhất chứa n và m. (1 ≤ n ≤ 1018, 2 ≤ m ≤ 20).
Output
In ra một dòng duy nhất là kết quả của bài toán khi chia lấy dư cho (109 + 7).
Example
Input 4 2 Output 5
Input 3 2 Output 3
Giải thích:
Có 5 trạng thái thỏa mãn là 1111, 0011, 1001, 1100, 0000.
| Được gửi lên bởi: | adm |
| Ngày: | 2019-02-23 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2020-02-18 14:35:42
test 15 là test ntn vậy ?? |
|
|
2019-03-12 02:29:12
Cứ bị sai sai ở test 15 ý! Ai chỉ dùm mik đc ko? |
