题目链接：点击打开链接
题意：给一个m一个d， 一个字符串a和b， 问在[a,b]范围内， 有多少个可以整除m的魔法数， 魔法数的定义是， 偶数位上都是d， 奇数位上都不是d。
思路：据说是典型的数位DP， 以前没做过数位DP， 感觉和DP差不多？
用d[i][j][p]表示当前到了第i位， 余数为j， p == 1表示目前和b串相等， p == 0表示已经比b串小了。 每次枚举第i位上放的数， 转移就行了。
区间也好弄， 我们可以先处理出小于等于b的所有情况ans1， 小于等于a的所有情况ans2， 那么ans1 - ans2， 别忘了， 还要看看a是不是符合条件，如果符合要加上。
细节参见代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 2000 + 10;
int T,n,m,dd,d[maxn][maxn][2],vis[maxn][maxn][2],kase=0;
inline int add(int& a, int b) {
a += b;
if(a >= mod) a -= mod;
}
char a[maxn], b[maxn];
bool ok() {
int res = 0;
for(int i=1;i<=n;i++) {
int v = a[i] - '0';
res = (res * 10 + v) % m;
if(i & 1) {
if(v == dd) return false;
}
else {
if(v != dd) return false;
}
}
if(!res) return true;
return false;
}
int dp(int i, int j, int p, char s[]) {
int& ans = d[i][j][p];
if(i == n+1) return j == 0;
if(vis[i][j][p] == kase) return ans;
vis[i][j][p] = kase;
ans = 0;
if(i & 1) {
for(int k=0;k<=9;k++) {
if(k == dd) continue;
if(!p) add(ans, dp(i+1, (j*10 + k)%m, 0, s));
else {
if(k == s[i]-'0') add(ans, dp(i+1, (j*10+k)%m, 1, s));
else if(k < s[i] - '0') add(ans, dp(i+1, (j*10+k)%m, 0, s));
}
}
}
else {
if(!p) add(ans, dp(i+1, (j*10+dd)%m, 0, s));
else {
if(dd == s[i]-'0') add(ans, dp(i+1, (j*10+dd)%m, 1, s));
else if(dd < s[i]-'0') add(ans, dp(i+1, (j*10+dd)%m, 0, s));
}
}
return ans;
}
int main() {
scanf("%d%d%s%s",&m,&dd,a+1,b+1);
n = strlen(b+1);
++kase;
int ans1 = dp(1, 0, 1, b);
++kase;
n = strlen(a+1);
int ans2 = dp(1, 0, 1, a);
if(ok()) --ans2;
int ans = (ans1 - ans2 + mod) % mod;//取模之后的两个数相减的处理
printf("%d\n",ans);
return 0;
}