题解 CF628D：数位DP

很显然是数位DP了。

这里首先化归成求对任意给定$n$，求小于等于$n$的魔法数（magic nubmer）的数量，然后即可求出$[L+1, R]$区间上的魔法数的数量，再对$L$进行特判即可得到结果。数位DP的详解在这里，给出了数位DP的常见模板，即记忆化搜索状态包括当前考虑位数$x$，前序影响决策的状态$st$和已枚举的前面所有数位是否均和$n$对应的位相等$op$。本题所需要计数的魔法数进行了两个限制，分别实现如下：

条件1

奇数位不能是$d$，偶数位只能是$d$。这个限制在我们每一步枚举所取数字的时候需要考虑位数$x$的奇偶即可：

当$x$是偶数位时，该位只能取$d$，但注意如果此时$op$为$1$且$n$对应的数位小于$d$，则不能选择任何数字。
当$x$是奇数位时，该位在一般数位DP选择范围的基础上应该挖去$d$。

注意由于是从最高位开始算奇数位或偶数位，其实这样直接算出来的答案并不严格是我们的定义。例如，考虑小于$99$的7-魔法数，按此法会将$7$考虑在内，虽然按定义并不如此。然而，由于我们最后要算的是一个区间的值，且题目保证$L$和$R$位数相等（初看奇怪的一个限制），这就意味着在这个区间内的奇数位/偶数位均可以按照$L$或者$R$从高到低的位数来看，而位数小于$L$和$R$的所有数字，只要保持计数时标准一致，无论是什么计数结果，都会在随后的减法中被消去。此法因而在本题是奏效的，也就不需要在$x$之外引入新的状态参量。

条件2

该数应当是$m$的倍数。根据模的性质，考虑将前序选择的数位模$m$后的值记录下来。这里其实有两种做法，可以像大多数题解一样逐步记录，也可以提前维护$10^k \mod m$的数组，从而直接记录前序数位真正的数值模$m$后的结果。考虑完所有数字后，需要判断前序和模$m$是否和$0$相等。

其他

其他确实就没什么了。要注意的是题目说的奇数位、偶数位都是以1为首位的，但是操作vector的时候下标是从0开始的，所以要么添一位，要么把题目里面的奇偶反过来。

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(register int i=from;i<=to;++i)
#define For(i,to) for(register int i=0;i<to;++i)
typedef long long ll;
inline ll read(){
    ll x=0; ll sign=1; char c=getchar();
    while(c>'9'  c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}

const long long M = 1000000007ll;
ll m, d;
vector<int> l, r;
ll f[2020][2020][2];
ll ten[2020]; // 10^i % m

void init() {
    ten[0] = 1;
    rep(i, 1, 2004) {
        ten[i] = ten[i - 1] * 10ll;
        ten[i] %= m;
    }
}

inline void read_vec(vector<int> &dim) {
    char c = getchar();
    while(c < '0'  c > '9') c = getchar();
    while(c >= '0' && c <= '9') {
        dim.push_back(c - '0');
        c = getchar();
    }
}

ll dp(int x, int st, int op, vector<int> &dim) {
    int s = dim.size();
    if (x == s) return (st == 0);

    ll &ret = f[x][st][op];
    if(ret > -1) return ret;
    ret = 0;
    int p = s - x - 1;
    if (!(x & 1)) {
        int maxx = op ? dim[x] : 9;

        rep(i, 0, maxx) {
            if (i == d) continue;
            int nst = (st + ((ten[p] * i) % m)) % m;
            ret += dp(x + 1, nst, op & (i == dim[x]), dim);
            ret %= M;
        }
    } else {
        if (op && dim[x] < d) return 0;
        else {
            int i = d;
            int nst = (st + ((ten[p] * i) % m)) % m;
            ret = dp(x + 1, nst, op & (i == dim[x]), dim);
        }
    }
    ret %= M;
    return ret;

}

ll solve(vector<int> &dim) {
    memset(f, -1, sizeof(f));
    return dp(0, 0, 1, dim);
}

int judge(vector<int> &dim) {
    ll sm = 0;
    int s = dim.size();
    For(i, s) {
        if(!(i & 1) && (dim[i] == d)) {
            return 0;
        }
        if((i & 1) && (dim[i] != d)) {
            return 0;
        }
        int p = s - i - 1;
        sm += ten[p] * dim[i];
        sm %= m;
    }
    if (sm != 0) return 0;
    else return 1;
}

int main() {
#ifdef D
    freopen("CF628D.in", "r", stdin);
#endif
    m = read(); d = read();
    read_vec(l); read_vec(r);

    init();

    ll res = solve(r) - solve(l) + judge(l);
    res %= M; res += M; res %= M;
    cout << res << "\n";

    return 0;
}