Educational Codeforces Round 8(D. Magic Numbers(数位DP))

时间:2022-12-16 10:32:38

题目链接:点击打开链接

题意:给一个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;
}