Educational Codeforces Round 8 D. Magic Numbers 数位DP

时间:2021-06-05 13:19:11

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;
}