Chữ Số Chẵn Lẻ Xen Kẽ

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

Một số nguyên dương được gọi là số xen kẽ nếu hai chữ số liên tiếp bất kỳ trong biểu diễn thập phân của nó (không tính các chữ số $0$ ở đầu) luôn có tính chẵn lẻ khác nhau (một chẵn, một lẻ). Các số có $1$ chữ số đều được coi là số xen kẽ.

Cho hai số nguyên dương $L, R$ và số nguyên dương $K$. Hãy đếm số lượng số xen kẽ trong đoạn $[L, R]$ đồng thời 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 $L, R, 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
1 30 3 8
10 50 2 11
Giới hạn
  • $1 \le L \le R \le 10^{18}$
  • $1 \le K \le 100$
Draft saved