Cặp Số Cộng Không Nhớ

Buổi 35 — Digit DP Dynamic Programming
Points
68
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho ba số nguyên dương $N, M, K$. Hãy đếm số lượng cặp số nguyên không âm $(x, y)$ thỏa mãn đồng thời các điều kiện sau:

  1. $0 \le x \le N$ và $0 \le y \le M$.
  2. Khi thực hiện phép cộng $x + y$ theo từng hàng chữ số ở hệ thập phân, không xảy ra phép nhớ nào (tức là tại mọi vị trí chữ số, tổng hai chữ số tương ứng của $x$ và $y$ đều nhỏ hơn $10$).
  3. Tổng $x + y$ chia hết cho $K$.

In kết quả chia dư cho $10^9 + 7$.

Dữ liệu vào
  • Một dòng chứa ba số nguyên $N, M, K$.
Dữ liệu ra
  • Một số nguyên duy nhất là kết quả bài toán chia dư cho $10^9 + 7$.
Ví dụ
Input Output
5 5 3 12
12 15 5 22
Giới hạn
  • $1 \le N, M \le 10^{18}$
  • $1 \le K \le 50$
Draft saved