题意：d magic number（0<=d<9）的意思就是一个数，从最高位开始奇数位不是d,偶数位是d
题目问，给a,b,m,d(a<=b,m<2000)问，a,b之间有多少个数满足既是d magic number，又可以被m整除
a,b的范围很大，都是2000位,且a,b的位数一样，这一点很重要
分析：这题一看又有取模，又是大整数，那肯定是要用数位dp做，
通常的数位dp，我们要解决（0，x)的区间中的答案，但是这个题不需要，
注意刚才我说过一点，a,b是位数相同的整数，假设solve()函数能解决x到和它同位的最小整数的区间范围内的答案
那么最终答案，就是solve(b)-solve(a)+is(a),
这样我们的工作就简单了，不需要统计位数比它小的数
我们从高位开始进行dp
下面定义状态
1: dp[i][j][1],代表现在处理到第 i 位 且前缀 i 位形成的整数n%m=j 的 方案数，且现在形成的整数等于上限
2: dp[i][j][0],代表现在处理到第 i 位 且前缀 i 位形成的整数n%m=j 的 方案数，且现在形成的整数小于上限
那么状态转移方程就很好想了
设字符串长度为n 那么时间复杂度是O(nm)的
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2e3+;
const int mod = 1e9+;
int dp[N][N][],num[N],m,d;
char a[N],b[N];
int solve(char *s)
{
int l=strlen(s+);
memset(dp,,sizeof(dp));
for(int i=; i<=l; ++i)
num[i]=s[i]-'';
for(int i=; i<=; ++i)
{
if(i==d)continue;
if(i<num[])++dp[][i%m][];
else if(i==num[])++dp[][i%m][];
}
for(int i=; i<=l; ++i)
{
if(i%==)
{
for(int j=; j<m; ++j)
{
int cur=(j*+d)%m;
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
if(d<num[i])
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
else if(num[i]==d)
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
}
}
else
{
for(int k=; k<; ++k)
{
if(k==d)continue;
for(int j=; j<m; ++j)
{
int cur=(j*+k)%m;
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
if(k<num[i])
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
else if(k==num[i])
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
}
}
}
}
return (dp[l][][]+dp[l][][])%mod;
}
int judge(char *s)
{
int l=strlen(s+),sum=;
for(int i=;i<=l;++i)
{
int x=s[i]-'';
if(i%&&x==d)return ;
if(!(i%)&&x!=d)return ;
sum=(sum*+x)%m;
}
if(!sum)return ;
return ;
}
int main()
{
scanf("%d%d%s%s",&m,&d,a+,b+);
int ans=(solve(b)-solve(a)+judge(a)+mod)%mod;
printf("%d\n",ans);
return ;
}