数位dp模板

Posted on | In

本质是记忆化搜索，一般求解区间[l,r]内有多少数字满足要求。我们可以拆分问题为solve(r)-solve(l-1)或solve(r)-solve(l)+judge(l)。注意到整个区间（例如[0,999]）在很多地方重复使用，所以对它记录。

例题：cf628D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int maxn=2e3+1;
const int maxm=2e3+1;
char a[maxn],b[maxn];
int num[maxn];
int m,d;
#define ll long long
ll dp[maxn][maxm];
int len;

int judge(const char* s,int lena){
    int mod=0;
    for(int i=1;i<=lena;i++){
        mod=(mod*10+s[i])%m;
        if((i&1)==0&&s[i]!=d){
            return 0;
        }
        if((i&1)&&s[i]==d)
            return 0;
    }
    return (mod==0);
}
int val[maxn];
ll dfs(int pos,int mod,bool limit){
    if(pos==len+1){
        /*if(mod==0){
            for(int i=1;i<pos;i++)
                printf("%d",val[i]);
            puts("");
        }*/
        return mod==0;
    }
    if(!limit&&dp[pos][mod]!=-1)
        return dp[pos][mod];
    int up=(limit?num[pos]:9);
    ll res=0;
    for(int i=0;i<=up;i++){
        int tmod=(mod*10+i)%m;  //模拟除法
        if((pos&1)&&(i==d))
            continue;
        if(!(pos&1)&&(i!=d))
            continue;
        //val[pos]=i;
        res=(res+dfs(pos+1,tmod,limit&&i==up))%MOD;
    }
    if(!limit)      //当处于非limit的时候，ans才是整个区间的值
        dp[pos][mod]=res;
    return res;
}

ll solve(const char* s,int lena){
    for(int i=1;i<=lena;i++)
        num[i]=s[i];
    len=lena;
    memset(dp,-1,sizeof(dp));
    return dfs(1,0,true)%MOD;
}

int main(){
    cin>>m>>d;
    cin>>(a+1);
    cin>>(b+1);
    int lena=strlen(a+1),lenb=strlen(b+1);
    for(int i=1;i<=lena;i++)
        a[i]-='0';
    for(int i=1;i<=lenb;i++)
        b[i]-='0';
    cout<<((solve(b,lenb)-solve(a,lena)+judge(a,lena))%MOD+MOD)%MOD<<endl;      //注意+MOD的操作，因为取MOD后可能会导致solve(a)>solve(b)
    return 0;
}