数位 dp 学习笔记
Silence_in_Sea
·
·
算法·理论
今天我们讲的是数位 dp。我们用 3 道例题来说这个算法。
题面：求出 1 \sim s 中含 3 的数的个数模 p 的结果，1 \le s \le 10^{100}。
以字符串形式读入 s。
令 n 为 s 的长度。
我们定义 dp_{i,j} 表示 i 位数含有 j 个 3 的种数（前导零可以）。
很容易想到先枚举 $i,j$。
在 $2 \sim n$ 枚举 $i$，在 $0 \sim i$ 枚举 $j$。
然后枚举这一位选的 $0 \sim 9$。
``dp[i][j]=(dp[i][j]+dp[i-1][j-(k==3)])%p;``
再分情况考虑，基础数位 dp 的思想。
对于第 $i$ 位推到 $a_i-1$。
有点难表述，具体见代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
char a[105];
int p,n;
int dp[105][105];
int main(){
cin>>(a+1)>>p;
n=strlen(a+1);
dp[1][0]=9%p;
dp[1][1]=1%p,dp[0][0]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=i;j++){
dp[i][j]=0;
for(int k=0;k<=9;k++){
if(j==0&&k==3) continue;
dp[i][j]=(dp[i][j]+dp[i-1][j-(k==3)])%p;
}
}
}
int ans=0,ok=0;
for(int i=1;i<=n;i++){
for(int j=0;j<a[i]-'0';j++){
if (j==3||ok) ans=(ans+dp[n-i][0])%p;
for(int k=1;k<=n-i;k++) ans=(ans+dp[n-i][k])%p;
}
if (a[i]=='3') ok=1;
}
cout<<(ans+ok)%p<<endl;
return 0;
}
```
题面：定义 $f(n)$ 是十进制下 $n$ 所有数位的和。
定义 $n \mod f(n) = 0$ 的 $n$ 为有趣数。
求出 $[1,n]$ 之间有趣数的个数。
$1 \le n \le 10^{18}$。
$sn$ 为 $n$ 的位数。
考虑数位 dp。
首先我们考虑在 $1 \sim 9 \times sn$ 中枚举所有位置数的和 $s$。
定义 $dp_{i,j,k,0/1}$ 为枚举到第 $i$ 位，数字和和 $s$ 取模为 $j$，与 $n$ 相等或比 $n$ 小。
枚举即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
char a[185];
int n;
long long ans,dp[20][185][185][2];
void f(int s){
memset(dp,0,sizeof(dp));
dp[0][0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=s;j++){
for(int k=0;k<s;k++){
if (dp[i][j][k][1]){
for(int t=0;t<=9&&t+j<=s;t++){
dp[i+1][j+t][(k*10+t)%s][1]+=dp[i][j][k][1];
}
}
if (dp[i][j][k][0]){
for(int t=0;t<a[i+1]-'0'&&t+j<=s;t++){
dp[i+1][j+t][(k*10+t)%s][1]+=dp[i][j][k][0];
}
if (j+a[i+1]-'0'<=s){
dp[i+1][j+a[i+1]-'0'][(k*10+a[i+1]-'0')%s][0]+=dp[i][j][k][0];
}
}
}
}
}
ans=ans+dp[n][s][0][0]+dp[n][s][0][1];
}
int main(){
cin>>(a+1);
n=strlen(a+1);
for(int i=1;i<=9*n;i++) f(i);
cout<<ans<<endl;
return 0;
}
```
来个炸裂点的题目。
题面：
定义 $x$ 为完美数，当且仅当 $x$ 中 $7$ 的个数和其他数字出现的个数都不一样，求 $[l,r]$ 范围内完美数的个数。
范围：$1 \le l,r \le 10^{18}$。
给作者干抽风的题目。
我们首先预处理 $c_{i,j}$ 表示 在 $i$ 个中选 $j$ 的种数。
我们假设 $calc(n)$ 表示 $1 \sim n-1$ 中完美数的个数。
我们首先把 $n$ 从低位到高位存在 $a$ 数组当中。
我们还是把问题分成两部分。
定义 $n$ 的位数为 $p$。
我们对于位数为 $p$ 的 $n$，用数位 dp 的思想，先处理位数为 $1 \sim p-1$ 的，再处理位数为 $n$ 的。
这一步其实比较简单理解了，具体见代码。
下面是重头戏：
我们定义 $calc2(n,c[])$ 为处理长度为 $n$ 的有些数位确定，有些数位不确定的一个数将不确定的位数填满是完美数的填法个数。
如果第 $i$ 位确定，则 $c_i$ 已经填了一个 $0 \sim 9$ 的数，否则 $c_i = -1$。
我们来讲 $calc2$ 如何实现。
首先统计出 $m$ 是不确定的位数，我们来枚举这个不确定的位数，同时定义 $t_x$ 为 $x$ 在确定位置中出现的次数。
然后我们在 $0 \sim m$ 枚举 $7$ 的个数为 $i$。
**我们定义 $dp_{j,i}$ 为目前非 $7$ 的个数为 $i$，只统计小于 $j$ 的数的所有非 $7$ 数个数均和 $7$ 的个数不同的种数。（这里的 $i$ 只是代指）**
我们很容易得出，在 $7$ 的个数为 $i$ 时，$ans$ 需要加上 $dp_{10,m-i} \times c_{m,i}$。
我们再来考虑如何求 $dp$。
首先我们从 $0 \sim 9$ 枚举 $j$。
如果 $j = 7$，很容易得出 $dp_{j+1,k} = dp_{j,k}$，因为根本在非 $7$ 的个数上不可能有改变。
如果 $j \not= 7$，我们就要考虑枚举**之前非 $7$ 的个数和现在准备要的 $j$ 的个数**，我们用 $k,l$ 表示。
我们首先保证 $l + t_j \not= t_7 + i$。
然后我们推出 dp 式 $dp_{j+1,k+l}$ 每次需要加上 $dp_{j,k} \times c_{k+l,l}$。
为什么呢？
因为这次多了 $l$ 个，有 $c_{k+l,l}$ 种插入方法，而本身有 $k$ 个，种数为 $dp_{j,k}$。
然后没了。