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

題意

現(xiàn)在定義d-magic數(shù)字，就是一個沒有前導(dǎo)0的數(shù)，d恰好僅出現(xiàn)在這個數(shù)的偶數(shù)位置。

然后現(xiàn)在給你m,d,a,b。問你在[a,b]內(nèi)，是m的倍數(shù)，且是d-magic的數(shù)字有多少個

答案需要 mod 1e9+7

題解：

比較顯然的數(shù)位dp

dp[len][mod][flag]表示現(xiàn)在長度是多少，現(xiàn)在的余數(shù)是多少，現(xiàn)在是否達(dá)到上界的方案數(shù)是多少

然后直接轉(zhuǎn)移就好了

這個讓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; }

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 8 D. Magic Numbers 数位DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。