数位DP算法概述及习题

前言

如果你对这篇文章可感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

一、数位DP概述

通常来说，数位 $dp$ 问题都是通过 $dfs$ 解决的，因为 $dfs$ 的做法更容易理解，也能一定地简化代码。

对于 $dfs$ 求解的数位 $dp$ 问题，其中设置的状态为 $f[pos][...]$，$pos$ 表示最后 $pos$ 位没有填，$...$ 表示的是从 $pos$ 位之前继承来的信息，然后 $f[pos][...]$ 的数值表示仅考虑这 $pos$ 位所对答案产生的贡献。

这 $...$ 所表示的状态通常需要根据题意来进行定义，比较个性化，也是数位 $dp$ 的核心难点。但数位 $dp$ 问题还是非常套路化的，你只需要根据题意想明白想要计算后 $pos$ 位的信息，到底需要从前几位继承哪些信息，想明白这个之后就可以直接套上 $dfs$ 的模板进行求解了。

下面的习题给出的都是非套路化问题，具有一定的难度，初学者建议先写一些模板题再来进行挑战。

最后给出 $dfs$ 问题的大致模板。(某一模板题的 $AC$ 代码)

#include <bits/stdc++.h> #define rep(i,a,b) for(int i = a; i <= b; i++) typedef long long ll; using namespace std; ll f[21][21][2010],a[30]; //左-右 ll dfs(int pos,int balan,int k,bool flag){ //位置 平衡点 左边继承来的数值 有无继承 if(pos == 0){ if(k == 0) return 1; else return 0; } if(!flag && f[pos][balan][k+1000] != -1) return f[pos][balan][k+1000]; ll ans = 0; int end = flag?a[pos]:9; rep(i,0,end){ ll tp = dfs(pos-1,balan,k+(pos-balan)*i,flag && i == end); ans += tp; } if(!flag) f[pos][balan][k+1000] = ans; return ans; } ll solve(ll n){ //求a数组 if(n == -1) return 0; int pos = 0; memset(a,0,sizeof a); while(n){ a[++pos] = n%10; n /= 10; } ll ans = 0; rep(i,1,pos) ans += dfs(pos,i,0,1); //对每一个平衡点分开求 ans -= pos-1; return ans; } int main() { //初始化 rep(i,0,20) rep(j,0,20) rep(k,0,2000) f[i][j][k] = -1; //读入 int _; scanf("%d",&_); while(_--){ ll L,R; scanf("%lld%lld",&L,&R); L--; printf("%lld\n",solve(R)-solve(L)); } return 0; }

---

二、数位DP系列习题

1. Daniel and Spring Cleaning

题意: 给出区间 $[l,r]$，查询多少对 $(a,b)$ 满足如下条件。$(0\le l\le r\le 10^9)$

$a+b=axorb$$l\le a\le r$$l\le b\le r$

思路: $CF$ $div2$ 的最后一题，比赛的时候有 $1h$ 来考虑这个问题。当时主要在思考这个题想要考察的是什么内容，思考过数位 $dp$，但是没有做过 $pair$ 类型的数位 $dp$，于是就没有从这个角度继续往下深入思考。因此剩下的大部分时间都在思考是不是一道结合某些数据结构的思维题，说实话，感觉数据结构开始限制我的思维了，什么题都老从数据结构考虑，这样非常容易被治，必须要改！

继续回到该题，此题其实想要询问的就是 $a\&b=0$ 的 $pair$ 对数。因此我们处理出一个 $solve(x,y)$ 函数，表示 $a\in [0,x],b\in [0,y]$，符合条件的 $pair$ 对数，所以最终答案就是 $solve(r,r)-solve(l-1,r)-solve(r,l-1)+solve(l-1,l-1)$。

接下来就是如何计算 $solve(x,y)$ 函数，其实维护 $x$ 和 $y$ 各自的数组，两个 $flag$，然后套上最基本的 $dfs$ 板子，稍微改一下就可以过了。

总结: 此题其实应该是两个数同时数位 $dp$ 的裸题，套上了一个最基本的容斥。而具体的函数实现过程还是比较套路的，并不难思考。

做不出来的原因也主要是没有从数位 $dp$ 这个角度继续往下深挖，是自己思考的片面性错失了 $AC$。

代码:

#include <bits/stdc++.h> #define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define rep(i,a,b) for(int i = a; i <= b; i++) typedef long long ll; typedef double db; const int N = 1e5+100; const int M = 1e5+100; const db EPS = 1e-9; using namespace std; void dbg() {cout << "\n";} template<typename T, typename... A> void dbg(T a, A... x) {cout << a << ' '; dbg(x...);} #define logs(x...) {cout << #x << " -> "; dbg(x);} ll f[40],a[40],b[40]; //左-右 ll dfs(int pos,bool flag1,bool flag2){ if(pos == 0) return 1; if(!flag1 && !flag2 && f[pos] != -1) return f[pos]; ll ans = 0; int end1 = flag1?a[pos]:1; int end2 = flag2?b[pos]:1; if(!flag1 && !flag2){ ans += 3ll*dfs(pos-1,0,0); } else if(!flag1){ rep(i,0,end2){ if(i == 0) ans += 2ll*dfs(pos-1,0,flag2 && i == end2); else ans += dfs(pos-1,0,flag2 && i == end2); } } else if(!flag2){ rep(i,0,end1){ if(i == 0) ans += 2ll*dfs(pos-1,flag1 && i == end1,0); else ans += dfs(pos-1,flag1 && i == end1,0); } } else{ rep(i,0,end1){ rep(j,0,end2){ if(i != 1 || j != 1) ans += dfs(pos-1,flag1 && i == end1,flag2 && j == end2); } } } if(!flag1 && !flag2) f[pos] = ans; return ans; } ll solve(ll x,ll y){ if(x == -1 || y == -1) return 0; int p1 = 0, p2 = 0; memset(a,0,sizeof a); memset(b,0,sizeof b); while(x){ a[++p1] = x%2; x /= 2; } while(y){ b[++p2] = y%2; y /= 2; } return dfs(max(p1,p2),1,1); } int main() { int _; scanf("%d",&_); memset(f,-1,sizeof f); while(_--){ ll L,R; scanf("%lld%lld",&L,&R); ll ans = solve(R,R)-solve(L-1,R)-solve(R,L-1)+solve(L-1,L-1); printf("%lld\n",ans); } return 0; }

2. Beautiful numbers

题意: 一个正整数被称为漂亮数，当且仅当其能够被其所有非零数位整除，现需要求 $[l,r]$ 中漂亮数的个数。$(1\le l\le r\le 9\ast 10^{18})$

思路: 整除所有非零数位，即整除非零数位的 $LCM$。因此我们需要在 $dfs$ 的过程中，记录出现数位的 $LCM$，以及记录当前数字的大小。

这里会出现一个问题，即当前数字非常大，直接记录不可行，因此我们需要将当前数字对 $2520$ 取模，即 $1～9$ 所有数的 $LCM$。思考到这一步，剩下的就是一些代码细节了，可以参考一下下述代码。

代码:

#include <bits/stdc++.h> #define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define rep(i,a,b) for(int i = a; i <= b; i++) #define LOG1(x1,x2) cout << x1 << ": " << x2 << endl; #define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl; #define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl; typedef long long ll; typedef double db; const int N = 1e5+100; const int M = 1e5+100; const db EPS = 1e-9; using namespace std; ll a[30],b[3000],tot,f[20][55][3000]; ll gcd(ll a,ll b){ return b == 0 ? a:gcd(b,a%b); } int find(ll x){ return lower_bound(b+1,b+1+tot,x)-b; } ll dfs(int pos,int lcm,ll m,bool flag){ if(pos == 0){ if(m%b[lcm] == 0) return 1; else return 0; } if(!flag && f[pos][lcm][m] != -1) return f[pos][lcm][m]; int end = flag?a[pos]:9; ll ans = 0; rep(i,0,end){ if(i == 0) ans += dfs(pos-1,lcm,(m*10ll+i)%(2520ll),flag && i == end); else{ ll tp = gcd(b[lcm],i); ll hp = b[lcm]*i/tp; int xp = find(hp); ans += dfs(pos-1,xp,(m*10ll+i)%(2520ll),flag && i == end); } } if(!flag) f[pos][lcm][m] = ans; return ans; } ll solve(ll n){ if(n == 0) return 1; int pos = 0; memset(a,0,sizeof a); while(n){ a[++pos] = n % 10; n /= 10; } return dfs(pos,1,0,1); } int main() { rep(i,1,((1<<9)-1)){ ll ans = 1; rep(j,1,9){ if(i&(1<<(j-1))){ ll tp = gcd(ans,j); ans = ans*j/tp; } } b[++tot] = ans; } sort(b+1,b+1+tot); tot = unique(b+1,b+1+tot)-b-1; rep(i,0,19) rep(j,0,50) rep(k,0,2900) f[i][j][k] = -1; int _; scanf("%d",&_); while(_--){ ll L,R; scanf("%lld%lld",&L,&R); L--; printf("%lld\n",solve(R)-solve(L)); } return 0; }

3. 吉哥系列故事——恨7不成妻

题意: 寻找区间 $[l,r]$ 中所有与 $7$ 无关的数字的平方和。与 $7$ 有关需要符合下述三个条件之一：

整数中某一位是 $7$整数的每一位加起来的和是 $7$ 的整数倍这个整数是 $7$ 的整数倍

$(1\le l\le r\le 10^{18})$

思路: 如果这题只是单纯地求个数，那就是一个普通数位 $dp$ 问题，但此题要求的是数字平方和，因此我们需要对每一个数位进行考虑。

当我们枚举 $pos$ 位时，先递归到 $pos-1$ 位，返回一个结构体 $B$，表示若 $pos-1$ 位前全为空时满足题意的 $cnt$、$sum1$、$sum2$，即个数、和、平方和。

设当前结构体为 $A$，因此 $A.cnt=A.cnt+B.cnt$，$A.sum1=A.sum1+B.sum1+B.cnt\ast 10^{pos-1}$，$A.sum2=A.sum2+B.sum2+10^{pos-1}\ast 10^{pos-1}+2\ast 10^{pos-1}\ast B.sum1$。

总结: 数位 $dp$ 的主要难点还是在于列出状态，然后采用递归的思想来思考如何根据第 $pos-1$ 位的答案推出 $pos$ 位的答案。

代码:

#include <bits/stdc++.h> #define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define rep(i,a,b) for(int i = a; i <= b; i++) #define LOG1(x1,x2) cout << x1 << ": " << x2 << endl; #define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl; #define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl; typedef long long ll; typedef double db; const int N = 1e5+100; const int M = 1e5+100; const ll mod = 1e9+7; const db EPS = 1e-9; using namespace std; struct Node{ ll cnt,sum1,sum2; //个数、和、平方和 }dp[25][10][10]; ll a[30]; ll pow_mod(ll a, ll b, ll p){ ll base = a, ans = 1; while(b){ if(b&1) ans = (ans*base)%p; base = (base*base)%p; b >>= 1; } return ans; } Node dfs(int pos, int pre1, int pre2, bool flag){ //pre1: 前面数位之和, pre2: 前面数位*贡献之和 //flag = 1, 前面为答案继承而来 if(pos == 0){ if(pre1 == 0 || pre2 == 0) return {0,0,0}; else return {1,0,0}; } if(!flag && dp[pos][pre1][pre2].cnt != -1) return dp[pos][pre1][pre2]; Node ans = {0,0,0}, tmp; int end = flag?a[pos]:9; rep(i,0,end){ if(i == 7) continue; tmp = dfs(pos-1, (pre1+i)%7, (pre2*10ll+i)%7, flag && i == end); ans.cnt = (ans.cnt+tmp.cnt)%mod; ans.sum1 = (ans.sum1+tmp.sum1+(tmp.cnt*(ll)i)%mod*pow_mod(10,pos-1,mod)%mod)%mod; ans.sum2 = (ans.sum2+tmp.sum2+(2ll*tmp.sum1*(ll)i)%mod*pow_mod(10,pos-1,mod)%mod)%mod; ans.sum2 = (ans.sum2+(ll)i*(ll)i*pow_mod(10,pos-1,mod)%mod*pow_mod(10,pos-1,mod)%mod*tmp.cnt%mod)%mod; } if(!flag) dp[pos][pre1][pre2] = ans; return ans; } ll solve(ll n){ int pos = 0; memset(a,0,sizeof a); while(n){ a[++pos] = n%(10ll); n /= 10ll; } return dfs(pos,0,0,1).sum2; } int main() { rep(i,0,20) rep(j,0,6) rep(k,0,6) dp[i][j][k].cnt = -1; int _; scanf("%d",&_); while(_--){ ll L,R; scanf("%lld%lld",&L,&R); L--; printf("%lld\n",(solve(R)-solve(L)+mod)%mod); } return 0; }

4. Balanced Numbers

题意: 查找区间 $[l,r]$ 中，符合如下条件的数字的个数：

所有出现过的偶数位，都出现了奇数次所有出现过的奇数位，都出现了偶数次

$(1\le l\le r\le 10^{19})$

思路: 这个问题主要的困难之处在于如何表示那些没有出现过的数字，如果用二进制状压的方式显然无法表示那些从未出现过的数字。

因此我们考虑使用三进制状压的方式，$0$ 表示没有出现过，$1$ 表示出现了奇数次，$2$ 表示出现了偶数次。

因此我们设置状态数组 $f[pos][S]$，表示还有 $pos$ 个位置没有填数，之前填了的数字继承下来的状态为 $S$，符合题干条件的数的个数。

代码:

#include <bits/stdc++.h> #define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define rep(i,a,b) for(int i = a; i <= b; i++) #define LOG1(x1,x2) cout << x1 << ": " << x2 << endl; #define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl; #define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl; typedef long long ll; typedef double db; const int N = 1e5+100; const int M = 1e5+100; const db EPS = 1e-9; using namespace std; ll f[21][60000],a[25],tp[25]; ll pow_mod(ll a,ll b){ ll base = a, ans = 1; while(b){ if(b&1) ans *= base; base *= base; b >>= 1; } return ans; } ll dfs(int pos,ll S,bool flag){ //S-各数位出现次数的状压 //flag只是表示是否表示了该位的全部情况 if(pos == 0){ int jud = 1; memset(tp,0,sizeof tp); int tot = -1; while(S){ tp[++tot] = S % 3; S /= 3; } rep(i,0,9){ if(tp[i] == 0) continue; if(i%2){ //奇数 if(tp[i] != 2) {jud = 0; break;} } else{ //偶数 if(tp[i] != 1) {jud = 0; break;} } } if(jud) return 1; else return 0; } if(!flag && f[pos][S] != -1) return f[pos][S]; int end = flag?a[pos]:9; ll ans = 0; rep(i,0,end){ if(i == 0 && S == 0) ans += dfs(pos-1,S,flag && i == end); //不能把前面的前导0继承过来 else{ int tot = -1, p = 0; ll hp = S; while(hp){ ++tot; if(tot == i) {p = hp%3; break;} hp /= 3ll; } hp = S; if(p == 0 || p == 1) hp += pow_mod(3,i); else hp -= pow_mod(3,i); ans += dfs(pos-1,hp,flag && i == end); } } // LOG3("pos",pos,"S",S,"ans",ans); if(!flag) f[pos][S] = ans; return ans; } ll solve(ll n){ if(n == 0) return 1; int pos = 0; memset(a,0,sizeof a); while(n){ a[++pos] = n % 10; n /= 10; } return dfs(pos,0,1); } int main() { ll base = pow_mod(3,10); // LOG1("base",base); rep(i,0,20) rep(j,0,base) f[i][j] = -1; int _; scanf("%d",&_); while(_--){ ll L,R; scanf("%lld%lld",&L,&R); L--; printf("%lld\n",solve(R)-solve(L)); } return 0; } /* 数位DP主要就是数位移动时，对答案贡献的求取 在数位移动时，要仔细考虑各个细节点，包括前导0等信息 */

5. Gift Pack

题意: 给出四个数，$L、R、A、B$，表示 $x\in [L,R],y\in [0,A],z\in [0,B]$，求 $(x\wedge y)+(y\&z)+(z\wedge x)$ 的最大值。$(0\le L\le R\le 10^{18},0\le A,B\le 10^{18})$

思路: 这个问题考察的是涉及三个数字的数位 $dp$，首先我们来思考一下如何表示状态。

此题是求取最大值，因此很明显需要从数位的角度入手进行考虑，所以状态的设置一定会包含各个数位的状态，我们另 $f[pos][p1][p2][p3][p4]$ 表示仅考虑最后 $pos$ 位，从前面转移来的状态为 $p1、p2、p3、p4$ 时答案的最大值。

$p1$ 为 $1$ 表示比 $L$ 大$p2$ 为 $1$ 表示比 $R$ 小$p3$ 为 $1$ 表示比 $A$ 小$p4$ 为 $1$ 表示比 $B$ 小

然后在 $dfs$ 的时候枚举 $pos$ 位放的值，然后更新答案即可。代码中将每个数拆成了二进制进行计算，因为仅考虑 $0、1$ 可以简化问题。

代码:

#include <bits/stdc++.h> #define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define rep(i,a,b) for(int i = a; i <= b; i++) #define LOG1(x1,x2) cout << x1 << ": " << x2 << endl; #define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl; #define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl; typedef long long ll; typedef double db; const int N = 1e5+100; const int M = 1e5+100; const db EPS = 1e-9; using namespace std; ll f[70][2][2][2][2],a1[70],a2[70],a3[70],a4[70]; ll pow_mod(ll a,ll b){ ll base = a, ans = 1; while(b){ if(b&1) ans *= base; base *= base; b >>= 1; } return ans; } ll dfs(int pos,bool f1,bool f2,bool f3,bool f4){ //比L大, 比R小, 比A小, 比B小 if(pos == 0) return 0; ll ans = f[pos][f1][f2][f3][f4]; if(ans != -1) return ans; int b1 = 0, b2 = 1, d1 = 0, d2 = 1, e1 = 0, e2 = 1; if(!f1 && a1[pos] != 0) b1 = 1; if(!f2 && a2[pos] != 1) b2 = 0; if(!f3 && a3[pos] != 1) d2 = 0; if(!f4 && a4[pos] != 1) e2 = 0; bool k1,k2,k3,k4; rep(i,b1,b2) rep(j,d1,d2) rep(k,e1,e2){ k1 = f1, k2 = f2, k3 = f3, k4 = f4; ll x = (i^j)+(j&k)+(k^i); x *= pow_mod(2,pos-1); // printf("********\n"); // LOG3("i",i,"j",j,"k",k); // LOG2("pos",pos,"x",x); if(i > a1[pos]) k1 = 1; if(i < a2[pos]) k2 = 1; if(j < a3[pos]) k3 = 1; if(k < a4[pos]) k4 = 1; ans = max(ans,x+dfs(pos-1,k1,k2,k3,k4)); } return (f[pos][f1][f2][f3][f4] = ans); } ll solve(ll L,ll R,ll A,ll B){ memset(a1,0,sizeof a1); memset(a2,0,sizeof a2); memset(a3,0,sizeof a3); memset(a4,0,sizeof a4); int pos = 0; while(L || R || A || B){ ++pos; a1[pos] = L & 1; a2[pos] = R & 1; a3[pos] = A & 1; a4[pos] = B & 1; L /= 2; R /= 2; A /= 2; B /= 2; } return dfs(pos,0,0,0,0); } int main() { int _; scanf("%d",&_); while(_--){ rep(i,0,65) rep(j,0,1) rep(k,0,1) rep(t1,0,1) rep(t2,0,1) f[i][j][k][t1][t2] = -1; ll L,R,A,B; scanf("%lld%lld%lld%lld",&L,&R,&A,&B); printf("%lld\n",solve(L,R,A,B)); } return 0; }

6. Gift Pack

题意: 给出区间 $[l,r]$，求所有数字中数位逆序对之和。$(1\le l\le r\le 10^8)$

思路: 这是一个涉及到组合计数的数位 $dp$ 问题，初次看到肯定觉得很棘手，但是我们可以将这个问题不断地进行分解。

我们先考虑 $pos$ 个位置，每个位置可以填 $[0,9]$ 时，所有可能的数的数位逆序对之和。这个问题不难处理，直接从 $pos$ 中取两个位置组成逆序队，其它位置任意取，答案为 $ans1(pos)=C(pos,2)\ast 45\ast 10^{pos-2}$。

然后再考虑如果 $pos$ 个位置，第一个位置不能为 $0$ 时的答案。我们先计算第一个位置和之后位置的贡献，再计算后面 $pos-1$ 位置产生的贡献。因此 $ans2(pos)=36\ast C(pos-1,1)\ast 10^{pos-2}+9\ast ans1(pos-1)$。

处理完这两个子问题之后，我们直接按照数位 $dp$ 的套路 $dfs$ 求解即可。如果不是很清楚，可以查看代码进行进一步了解。

思路:

#include <bits/stdc++.h> #define rep(i,a,b) for(int i = a; i <= b; i++) typedef long long ll; using namespace std; void dbg() {cout << "\n";} template<typename T, typename... A> void dbg(T a, A... x) {cout << a << ' '; dbg(x...);} #define logs(x...) {cout << #x << " -> "; dbg(x);} ll a[30],POS; //快速幂 ll calc(ll a,ll b){ if(b < 0) return 0; ll ans = 1, base = a; while(b){ if(b&1) ans *= base; base *= base; b >>= 1; } return ans; } //数字长度为pos且第一个数字不为0 ll calc1(ll pos){ ll ans = 0; ans += 36ll*(pos-1ll)*calc(10,pos-2); //第一个数不为0，后续数字与其组成的贡献 ans += 9ll*(pos-2ll)*(pos-1ll)*45ll*calc(10,pos-3)/2ll; //除第一个数字之外的贡献 return ans; } //数字长度为pos且第一个数字可以为0 ll calc2(ll pos){ return pos*(pos-1ll)*45ll*calc(10,pos-2)/2ll; } ll dfs(int pos,int *base,bool flag,ll hp){ ll ans = 0; if(pos == 0){ return hp; } if(!flag){ ans = calc2(pos); rep(i,0,8) ans += (ll)base[i]*(ll)pos*(ll)(9-i)*calc(10,pos-1); ans += hp*calc(10,pos); return ans; } int end = a[pos]; ll tmp = 0; rep(i,0,end){ if(POS == pos && i == 0) continue; //保证起始位不为0 if(i > 0) tmp += (ll)base[i-1]; base[i]++; ans += dfs(pos-1,base,flag && i == end,hp+tmp); base[i]--; } return ans; } ll solve(ll n){ if(n <= 9) return 0; POS = 0; memset(a,0,sizeof a); while(n){ a[++POS] = n%10ll; n /= 10ll; } int base[11]; rep(i,0,9) base[i] = 0; ll ans = dfs(POS,base,1,0); rep(i,2,POS-1) ans += calc1(i); return ans; } int main(){ int _; scanf("%d",&_); rep(Ca,1,_){ ll x,y; scanf("%lld%lld",&x,&y); x--; printf("Case %d: %lld\n",Ca,solve(y)-solve(x)); } }