求l,r之间偶数位上都是d且原数整除m的数。
dp[x][sum]表示前x位原数是sum，转移的时候偶数位只转d，奇数位不转d就行。
下附代码：
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const ll MOD=1e9+7; 5 ll dp[2005][2005],m,d,ans,bit[2005],len; 6 char l[2005],r[2005]; 7 ll dfs(int pos, ll sum, bool flag) { 8 if (pos==-1) return sum==0; 9 if (!flag && dp[pos][sum]!=-1) return dp[pos][sum]; 10 ll res=0; 11 for (int i=0, up=flag?bit[pos]:9; i<=up; ++i) { 12 if ((len-pos)&1) { if (i==d) continue; } 13 else { if (i!=d) continue; } 14 (res+=dfs(pos-1, (sum*10+i)%m, flag&&(i==up)))%=MOD; 15 } 16 return flag?res:dp[pos][sum]=res; 17 } 18 ll calc(char *x) { 19 len=strlen(x); 20 for (int i=0; i<len; ++i) bit[len-i-1]=x[i]-'0'; 21 return dfs(len-1, 0, 1); 22 } 23 24 int check() { //单独处理l 25 ll sum=0; len=strlen(l); 26 for (int i=0; i<len; ++i) { 27 int x=l[i]-'0'; 28 if ((i+1)&1) { if (x==d) return 0; } 29 else { if (x!=d) return 0; } 30 (sum=sum*10+x)%=m; 31 } 32 return sum==0; 33 } 34 35 int main() { 36 memset(dp, -1, sizeof(dp)); 37 scanf("%lld%lld", &m, &d); 38 scanf("%s", l); 39 scanf("%s", r); 40 ans=calc(r)-calc(l); 41 ans+=check(); 42 printf("%lld ", (ans+MOD)%MOD); 43 return 0; 44 }