Đếm Số Có Tổng Chữ Số Bằng S
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Cho hai số nguyên ~N~ và ~S~. Hãy đếm số lượng số nguyên dương trong đoạn ~[1, N]~ có tổng các chữ số (trong hệ thập phân) đúng bằng ~S~.
Kết quả lấy modulo ~10^9 + 7~.
Input
Một dòng duy nhất gồm hai số nguyên ~N~ và ~S~ (~1 \le N \le 10^{18}~, ~1 \le S \le 162~).
Output
In ra kết quả modulo ~10^9 + 7~.
Ví dụ
Input 1
20 2
Output 1
3
Giới hạn
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | 15% | ~N \le 10^6~ |
| 2 | 25% | ~N \le 10^{12}~ |
| 3 | 60% | ~N \le 10^{18}~ |
Gợi ý
Sử dụng Digit DP với trạng thái ~(\text{vị trí}, \text{tổng chữ số đã chọn}, \text{tight}, \text{started})~, trong đó:
- ~\text{tight}~: liệu các chữ số đã chọn có bị ràng buộc bởi giới hạn trên không.
- ~\text{started}~: đã bắt đầu điền chữ số khác ~0~ chưa (để tránh đếm số ~0~ đứng đầu).
Bình luận