0.引入的引入

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。

而数位DP，就是解决在区间[L,R][L,R]这个范围内，求满足某种约束的数字的数量或总和或乘积或平方这一类问题。

两种写法，一种是记忆化搜索，一种是迭代写法。这里是记忆化搜索，优点是好写好维护。

1.由例题引入数位DP

数位DP有一个通用的技巧，就是利用前缀和的思想，先求出[1,R][1,R]区间的满足约束的数字答案，再处理[1,L−1][1,L-1]的满足约束的数字答案，这样Ans[R]−Ans[L−1]Ans[R]-Ans[L-1]所求得的区间就是[L,R][L,R]区间的答案。

所以我们要求解的内容就变为了求[0/1,x][0/1,x]这一区间满足限定的答案，其实0/1表示可以区间取0或1作为开始

在代码中表现为

  • a[1...len]a[1...len]表示将数分解成R进制（一般为10进制或者2进制），用数组存储，表示数字分解为R进制下的第aia_i位，或者也可以说是系数
  • 最高位为a[len]a[len]，最低位为a[1]a[1]。
    例如我们将1145转化为10进制下的数位
1
2
pos:1 2 3 4
a:  1 1 4 5

代码写起来是这样的

1
2
3
4
5
6
7
8
9
ll solve(ll x){
    int len=0;
    while (x>0)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(...)
}

填数的话我们从高位往低位去填

例题：[洛谷P4999]

求解区间[L,R][L,R]中所有数的数位和之和
数位和就是把一个数所有数位上的数字加起来，例如1145->1+1+4+5=11

既然是记忆化搜索，我们一层一层搜索，我们先来定义一些状态能够跑起来再说。

  • pospos：整形变量，表示当前枚举的位置，一般从高位到低位

我们假设x=2048x=2048，用？表示仍未填写的位数,目前一位都没有填，所以是???
我们从高位往低位取填，第一步填写最高位，很显然我们只能填[0,2][0,2]的数

  • 若填写[0,1][0,1]的数，则我们可以从[0,1999][0,1999]都可以取到
  • 若填写22，则我们只能从[2000,2048][2000,2048]，我们发现对于一般情况，可以做到[1,9][1,9]随便填写，但是这里因为有着上界的限制，2???后面的三位只能最高填到048，所以我们需要记录一个变量limitlimit来表示当前数位是否可以任意填写

  • limitlimit：布尔变量，表示当前的第pos位是否收到取值限制
    • 当为True表示取的数不能大于当前的数位，为true时表示[pos+1,R][pos+1,R]取的都是aia_i的限制，

当我们搜索到pos=0pos=0的时候表示所有数位填写完毕，这是一个递归边界，我们需要返回枚举的结果，在传递结果的时候我们需要一个变量进行存储

  • sumsum: 整形变量，表示[pos+1,len][pos+1,len]填写完毕所获得的结果答案，这个题表示的是数位和

以上是最普通的暴搜，但是鉴于我们有着101810^{18}的上界，所以我们需要暴力枚举。

我们观察枚举的数位，我们发现如下案例

1
03?? 12?? 30?? 21??

我们发现其实他们的结果都是一样的！因为对于后面未填写的结果，只要没有上界的限制，都会取到[0,99][0,99]，因为我们关注的是数位和，所以只需要前面数字数位和一样，并且没有限制(limit=falselimit=false)就可以记录答案！

设状态f[pos][sum]f[pos][sum]

  • 位置[pos+1,len][pos+1,len]已经填写完毕，在没有最高数位限制的情况下，我对于[1,pos][1,pos]进行任意填写，满足约束的所有数位和。


我们可以大致写出记忆化搜索的代码啦，这里我们先初始化ff数组为−1-1，即全为非法状态。

  • 小技巧，~xx是按位取反操作，该操作返回0时当且仅当x=−1x=-1，用来判断值是否为−1-1
    代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll dfs(int pos,bool limit,int sum){
    if(!pos){//递归边界为0
        return sum;
    }
    if(!limit&&~f[pos][sum]){//如果没有最高限制并且有记录
        return f[pos][sum];
    }
    int up;
    if(limit){//如果有最高位限制
        up=a[pos];
    }else up=9;//baka
    ll ret=0;
    for(int i=0;i<=up;i++){
        //要求当这个位取到最高位并且limit也是1才能往下继续limit
        ret=(ret+dfs(pos-1,limit&&i==up,sum+i))%mod;
    }
    if(!limit){//如果没有最高位限制就是一般性答案，可以记录
        f[pos][sum]=ret;
    }
    return ret;
}

等会，初始状态怎么办，limitlimit怎么处理！

我们想一想，我们发现对于上界最大取多少完全取决于limitlimit，如果limit=falselimit=false则上界可以取到99，如果limit=truelimit=true，则上界只能取到数位的值。

也就是说，如果我们初始状态我们设limit=falselimit=false的话，那最高位的枚举就会取到[1,9][1,9]，这样答案就会错误！

所以我们在初始化时limit=truelimit=true，pos=lenpos=len，sum=0sum=0。

代码solve函数即如下

1
2
3
4
5
6
7
8
9
10
ll solve(ll x){
    int len=0;
    while (x>0)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,true,0);
    //先从最高位开始，肯定有limit=1不然如果出来个不是9的最高位直接炸了
}

那么如何证明我这个并没有退化成暴搜呢

考虑ff状态数量，数字上界为101810^{18}，18个9时是sumsum最大，结果即为9×18+19 \times 18 + 1即163

总状态数即为19×163=309719 \times 163=3097，很少

计算复杂度时，我们考虑一个状态计算值时，需访问多少个状态，由数位一般性取值下为[0,9][0,9]，容易得到为10个状态。

可得计算出ff的时间复杂度为O(len×sum×R)O(len\times sum \times R)，也就是共有3097×10=309703097\times 10=30970个状态

是否会存在limitlimit为truetrue的节点过多导致状态记录不符合一般性退化成暴力搜索呢，我们显然可以发现

limit=truelimit=true在全部数位都是truetrue的情况下只能是一条链！链的长度就是lenlen，也就是说扣除最右边那条链，剩下的状态数量也是不会超过len×sum×Rlen\times sum \times R的，黑色部位的连边我们默认认为O(1)O(1)复杂度，就是假设已经算完。

所以我们为什么要设置limit=falselimit=false才能使用状态？

  • 多组数据下这个状态是可以复用的
  • 我们发现当limit=truelimit=true属于是特殊情况，这种情况出现只是因为数位的限制，这些状态不符合一般性能取到[0,9][0,9]的情况，这些情况我们是不能复用的，记录上还浪费我们的空间。
    所以你不会在任何数位dp题目中见到将limitlimit作为状态的

完整代码如下,一般来说我们是需要开long long的

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
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
int T;
const ll ML=20,mod=1e9+7,MZ=9*18+5;
int a[ML],f[ML][MZ];
ll dfs(int pos,bool limit,int sum){
    if(!pos){//递归边界为0
        return sum;
    }
    if(!limit&&~f[pos][sum]){//如果没有最高限制并且有记录
        return f[pos][sum];
    }
    int up;
    if(limit){//如果有最高位限制
        up=a[pos];
    }else up=9;//baka
    ll ret=0;
    for(int i=0;i<=up;i++){
        //要求当这个位取到最高位并且limit也是1才能往下继续limit
        ret=(ret+dfs(pos-1,limit&&i==up,sum+i))%mod;
    }
    if(!limit){//如果没有最高位限制就是一般性答案，可以记录
        f[pos][sum]=ret;
    }
    return ret;
}
ll solve(ll x){
    int len=0;
    while (x>0)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,true,0);
    //先从最高位开始，肯定有limit=1不然如果出来个不是9的最高位直接炸了
}
int main(){
    memset(f,-1,sizeof(f));
    cin>>T;
    while (T--)
    {
        ll l,r;
        cin>>l>>r;
        ll ans=(solve(r)-solve(l-1)+mod)%mod;
        cout<<ans<<endl;
    }
    
    return 0;
}

例题实践

例题1——windy数

  • 不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 aa 和 bb 之间，包括 aa 和 bb ，总共有多少个 windy 数？(1≤a≤b≤2×1091\le a \le b \le 2\times 10^9)
    我们发现有了相邻数位的约束，
    所以我们需要加上前面是否有前导0——lead0lead0和上一位填写的数字——lastlast

注意lastlast初始赋值不能赋值−1-1！不然最高位就取不到−1,0,1-1,0,1。

我们可以知道约束条件体现在[pos+1,len][pos+1,len]上，[1,pos][1,pos]任意填写，这里的约束条件就是lastlast

故设状态f[pos][last]f[pos][last]，表示[pos+1,len][pos+1,len]已经填写完毕，[1,pos][1,pos]任意填写，上一位数为lastlast的情况下windy数共有多少

不难写出代码

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
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int MN=15,INF=1e9+7;
int f[MN][MN],a[MN];
//f[pos,last]表示[pos+1,len]都已经填写，且pos+1位填写的是last
//的windy数数量，即以last开头的windy数的数量
ll dfs(int pos,bool limit,bool lead0,int last){
    if(!pos) return 1;
    if(!limit&&last!=INF&&~f[pos][last]){
	    //如果无限制并且last填链并且状态合法
        return f[pos][last];
    }
    int up,ret=0;
    if(limit){
        up=a[pos];
    }else up=9;
    for(int i=0;i<=up;i++){
        if(lead0){//如果是前导0表示还没填数，不能约束下一个数！
	        //所以i=0时我们将last传递就行，如果不是0就传递i
            ret=ret+dfs(pos-1,limit&&i==up,lead0&&i==0,i==0 ? last : i);
        }else if(abs(last-i)>=2){
            ret=ret+dfs(pos-1,limit&&i==up,0,i);
        }
    }
    if(!limit&&last!=INF){
	    //如果前一位填并且无限制适用于一般性情况
        f[pos][last]=ret;
    }
    return ret;
}
int solve(ll x){
    int len=0;
    while (x>0)
    {
        a[++len]=x%10;
        x/=10;
    }
    //这里前导0也要设置不然前导0的情况算不上，和上面例0的情况差不多
    return dfs(len,1,1,INF);
}
int main(){
    memset(f,-1,sizeof(f));
    ll l,r;
    cin>>l>>r;
    cout<<solve(r)-solve(l-1);
    return 0;
}

例题2:花神的数论题P4317

设sum(i)\text{sum}(i) 表示ii 的二进制表示中11 的个数。给出一个正整数NN ，花神要问你∏i=1Nsum(i)\prod_{i=1}^{N}\text{sum}(i) ，也就是sum(1)∼sum(N)\text{sum}(1)\sim\text{sum}(N) 的乘积。

注意这题的不同点是求乘积

我们仔细想一下其实差不多，我们在统计递归树子树答案结果用的是和，这里我们只需要改为乘就可以了

但是，如果我们仍设ret=0ret=0的话那0×x=00\times x=0啊，没关系只需要设ret=1ret=1就可以了

类似例子0，但这里是二进制，只有1，而1出现次数就是数码和

故设状态f[pos][cnt]f[pos][cnt]，表示[pos+1,len][pos+1,len]体经填写了cntcnt个1，[1,pos][1,pos]填写，所有合法方案的乘积

故不难写出代码

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
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int mod=1e7+7,MN=110;
ll f[MN][MN],a[MN];
ll dfs(int pos,bool limit,int cnt){
    if(!pos){
        return max(cnt,1);
    }
    if(!limit&&~f[pos][cnt]){
        return f[pos][cnt];
    }
    ll up,ret=1;
    if(limit){
        up=a[pos];
    }else up=1;
    for(int i=0;i<=up;i++){
        ret=(ret*dfs(pos-1,limit&&i==up,cnt+(i==1)))%mod;
    }
    if(!limit){
        f[pos][cnt]=ret;
    }
    return ret;
}
ll solve(ll x){
    int len=0;
    while (x>0)
    {
        a[++len]=x%2;
        x/=2;
    }
    return dfs(len,true,0);
}
int main(){
    memset(f,-1,sizeof(f));
    ll x;
    cin>>x;
    cout<<solve(x);
    return 0;
}

例题3:启示录

古代人认为666666 是属于魔鬼的数。
不但如此，只要某数字的十进制表示中有三个连续的66，古代人也认为这是个魔鬼的数，比如666,1666,6663,16666,6660666666,1666,6663,16666,6660666 等等。
古代典籍中经常用“第XX 小的魔鬼的数”来指代这些数，这给研究人员带来了极大的不便。
现在请编写一个程序，可以实现输入XX，输出对应的魔鬼数。

不难设状态为f[pos][lst1][lst2]f[pos][lst1][lst2]，表示[pos+1,len][pos+1,len]填写完毕，对于pospos的上一位lst1lst1是否是6（lst1=0/1lst1=0/1，bool变量），对于pospos的上上一位lst2lst2是否为6（lst2=0/1lst2=0/1)，的蘑菇数的个数。

不难有dfs：

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
ll f[MN][2][2];

ll dfs(int pos,bool lt1,bool lt2,bool lim){
    if(!pos) return 1;
    if(!lim&&~f[pos][lt1][lt2]) return f[pos][lt1][lt2];
    int up;
    if(lim) up=a[pos];
    else up=9;
    ll ret=0;
    for(int i=0;i<=up;i++){
        if(lt1&&lt2&&i==6) continue;//蘑菇数状态重复了，要排了
        ret+=dfs(pos-1,i==6,lt1,lim&&i==up);
    }
    if(!lim) f[pos][lt1][lt2]=ret;
    return ret;
}

ll solve(ll x){
    int len=0;
    while(x>0){
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1);
}

考虑第xx小如何求出，不难发现值域上对于次数，右边界扩大那么一定有单调性。我们实际上可以考虑在值域上二分，每一次二分DFS求出个数，mid+1−dfsmid+1-dfs即为次数，我们要求二分恰好到xx，那么当mid+1−dfs≥xmid+1-dfs\ge x时才能更新rr，否则更新ll

那么代码如下：

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr int MN=20;
int a[MN],T;
ll f[MN][2][2];

ll dfs(int pos,bool lt1,bool lt2,bool lim){
    if(!pos) return 1;
    if(!lim&&~f[pos][lt1][lt2]) return f[pos][lt1][lt2];
    int up;
    if(lim) up=a[pos];
    else up=9;
    ll ret=0;
    for(int i=0;i<=up;i++){
        if(lt1&&lt2&&i==6) continue;
        ret+=dfs(pos-1,i==6,lt1,lim&&i==up);
    }
    if(!lim) f[pos][lt1][lt2]=ret;
    return ret;
}

ll solve(ll x){
    int len=0;
    while(x>0){
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1);
}


int main(){
    memset(f,-1,sizeof(f));
    cin>>T;
    while(T--){
        int x;
        cin>>x;
        ll l=665,r=1e18;
        while(l+1<r){
            ll mid=(l+r)>>1;
            if(mid+1-solve(mid)<x){
                l=mid;
            }else r=mid;
        }
        cout<<l+1<<'\n';
    }
    return 0;
}

形参设定

以下为记忆化搜索dfsdfs常设定的形参

  • pospos：整形，表示当前枚举的位置，一般从高到低
  • limitlimit：布尔，表示当前pospos位是否收到限制
    • 为truetrue时表示当前取得位数不能大于a[pos]a[pos]，只有在[pos+1,len][pos+1,len]的值填写的数都是aia_i的时候该值才能为truetrue，在递归树上表示为一条链
  • lastlast：整形，表示上一位填写的值（即pos+1pos+1填写的值）
  • lead0lead0：布尔，表示是否有前导零，即在len→(pos+1)len\rightarrow (pos+1)的位置是否都是前导0
    • 基于尝试，我们往往认为一个数没有前导0，最高位不能为0.在只有没有前导0的时候，才能够计算0的贡献，那么前导0什么时候会和答案有关，有以下情况
      • 统计0的出现次数
      • 相邻数值的差值
      • 以最高位为起点确定的奇偶位
  • sumsum：整形，表示len→(pos+1)len\rightarrow (pos+1)的数位和
  • rr：整形变量，表示整个数前缀取模mm所得的余数
    • 这种情况下一般用在约束中出现了能被mm整除
  • stst：整形变量，用于状态压缩
    • 对一个集合的数在数位上的出现次数的奇偶性有要求时，其二进制形式就可以表示每个数出现的奇偶性
    • 3

参考

GhostXL算法学习笔记——数位DP