TPCLKNUM - Lucky Number
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
"Ngày xửa ngày xưa, từ rất lâu rồi, từ khi ông nội của ông nội ta kể cho ông nội ta nghe, tương truyền trong nhân gian rằng, nếu ai đếm được số số may mắn có độ dài N và có ít nhất K chữ số 6 đứng cạnh nhau thì sẽ không phải chịu kiếp đi cài win dạo mà được làm coder hạnh phúc đến trọn đời"
Nghe lời của bố kể lại, Mew quyết tâm giải bằng được bài toán trên, lần này máy tính quá khủng (Intel Core i10) nhưng lại không cài FPC hay C++ nên Mew đành nhờ các bạn giải hộ.
Input
Gồm 2 số nguyên N và K
Output
Một số duy nhất là đáp án lấy theo modulo 10^9+7.
Example
Input: 4 3 1 1 8 5 100000 666 Output: 18 1 3420 505047023
Giải thích
N = 4, K = 3, có 18 số thỏa mãn : 1666, 2666, 3666, 4666, 5666, 6660, 6661, 6662, 6663, 6664, 6665, 6666, 6667, 6668, 6669, 7666, 8666, 9666.
Giới hạn :
- 30% số test có N, K <= 1000.
- 20% số test có K = 1
- 50% còn lại N,K <= 100000
- Người up: mr_pyn_hp9x
- Nguồn bài: Ðề thi chọn đội tuyển Hải Phòng