D. Magic Numbers
题目连接：
http://www.codeforces.com/contest/628/problem/D
Description
Consider the decimal presentation of an integer. Let's call a number d-magic if digit d appears in decimal presentation of the number on even positions and nowhere else.
For example, the numbers 1727374, 17, 1 are 7-magic but 77, 7, 123, 34, 71 are not 7-magic. On the other hand the number 7 is 0-magic, 123 is 2-magic, 34 is 4-magic and 71 is 1-magic.
Find the number of d-magic numbers in the segment [a, b] that are multiple of m. Because the answer can be very huge you should only find its value modulo 109 + 7 (so you should find the remainder after dividing by 109 + 7).
Input
The first line contains two integers m, d (1 ≤ m ≤ 2000, 0 ≤ d ≤ 9) — the parameters from the problem statement.
The second line contains positive integer a in decimal presentation (without leading zeroes).
The third line contains positive integer b in decimal presentation (without leading zeroes).
It is guaranteed that a ≤ b, the number of digits in a and b are the same and don't exceed 2000.
Output
Print the only integer a — the remainder after dividing by 109 + 7 of the number of d-magic numbers in segment [a, b] that are multiple of m.
Sample Input
2 6
10
99
Sample Output
8
Hint
题意
现在定义d-magic数字，就是一个没有前导0的数，d恰好仅出现在这个数的偶数位置。
然后现在给你m,d,a,b。问你在[a,b]内，是m的倍数，且是d-magic的数字有多少个
答案需要 mod 1e9+7
题解：
比较显然的数位dp
dp[len][mod][flag]表示现在长度是多少，现在的余数是多少，现在是否达到上界的方案数是多少
然后直接转移就好了
这个让L--很麻烦，所以我直接就判断L这个位置合不合法就好了，如果合法，我就直接让答案++就好了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+5;
const int mod = 1e9+7;
int dp[maxn][maxn][2];
int vis[maxn][maxn][2];
char s[maxn];
int m,d,len;
int check()
{
int mm = 0;
for(int i=1;i<=len;i++)
{
mm = (mm+s[i]-'0')%m;
if(i%2==1&&(s[i]-'0')==d)
return 0;
if(i%2==0&&(s[i]-'0')!=d)
return 0;
}
if(mm!=0)return 0;
return 1;
}
void update(int &a,int b)
{
a = (a+b)%mod;
}
int solve(int Len,int Mod,int Flag)
{
if(Len==len+1)return Mod==0?1:0;
if(vis[Len][Mod][Flag])return dp[Len][Mod][Flag];
vis[Len][Mod][Flag]=1;
int st=0,ed=0;
if(Flag!=0)ed=9;else ed=s[Len]-'0';
if(Len==1)st=1;else st=0;
if(Len%2==0)
{
if(ed>=d)
{
int Flag2 = Flag|(d<(s[Len]-'0'));
update(dp[Len][Mod][Flag],solve(Len+1,(Mod*10+d)%m,Flag2));
}
}
else
{
for(int i=st;i<=ed;i++)
{
if(i==d)continue;
int Flag2 = Flag|(i<(s[Len]-'0'));
update(dp[Len][Mod][Flag],solve(Len+1,(Mod*10+i)%m,Flag2));
}
}
return dp[Len][Mod][Flag];
}
int main()
{
scanf("%d%d",&m,&d);
scanf("%s",s+1);
len = strlen(s+1);
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
int ans1 = solve(1,0,0),ans2=0;
if(check())ans2++;
scanf("%s",s+1);
len = strlen(s+1);
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
ans2 += solve(1,0,0);
int ans=(ans2-ans1)%mod;
if(ans<0)ans+=mod;
cout<<ans<<endl;
}