题目： 这里
题意：给定数字m， d 和2个长度小于2000 的数字a, b，问区间[a, b]内有多少个数偶数位只包含数字d，奇数位都不含有数字d，且能被m整除。
思路：
数位dp，dp[i][j] 表示前 i 个数字模为 j 的方法数，分类讨论 i 是偶数位还是奇数位就可以了。
代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const ll MOD = 1e9+7; 6 const int N = 2020; 7 8 char a[N], b[N]; 9 int m, n; 10 int dg[N]; 11 ll f[N][N]; 12 13 inline ll add(ll x, ll y) { 14 x = x + y; 15 return x >= MOD ? x-MOD : x; 16 } 17 18 ll dfs(int i, int s, bool flag, bool e) { // dp[i][s] , flag 表示奇数还是偶数，e代表边界 19 if(i == -1) return s == 0; 20 if(!e && ~f[i][s]) return f[i][s]; 21 ll res = 0LL; 22 int u = e ? dg[i] : 9; 23 for(int d = 0; d <= u; ++d) { 24 if(flag == 1 && d == n) continue; 25 if(flag == 0 && d != n) continue; 26 res = add(res, dfs(i-1, (s*10+d)%m, flag^1, e && d==u)); 27 } 28 return e ? res : f[i][s] = res; 29 } 30 31 void deal(int& len) { 32 for(int i = 0; i < len; ++i) { 33 if(dg[i] == 0) dg[i] = 9; 34 else { 35 --dg[i]; 36 break; 37 } 38 } 39 return ; 40 } 41 42 ll solve(char c[], bool fg) { 43 int len = strlen(c); 44 for(int i = 0; i < len; ++i) dg[i] = c[len-1-i] - '0'; 45 if(fg) deal(len); 46 return dfs(len-1, 0, 1, 1); 47 } 48 49 int main() 50 { 51 scanf("%d %d", &m, &n); 52 scanf("%s %s", a, b); 53 memset(f, -1, sizeof f); 54 printf("%I64d ", add(solve(b, 0) - solve(a, 1), MOD)); 55 return 0; 56 }