題目連結:點選打開連結
題意:給一個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;
}