数位 dp 小结
数位 dp 是一种题型类的 dp，具有极强的典型性，有较为固定的 dp 模式。
数位 dp 擅长解决形如「\(\le n\) 的数中，在 \(B\) 进制表示下满足建立在各位数之间的某种关系的数有多少个」的问题。注明，通常会采用 \([l,r]\) 中满足条件的数的个数，那么显然根据 \([l,r]=[1,r]-[1,l-1]\) 就可以转化成上述形式。
总的来说，数位 dp 基础题型有两类，解决方式有两种。
基础题型分为：
- 求 \(B\) 进制表示不包含某个或某些子串 \(s'\) 的数的个数
- 求各位和为 \(s\) 的数的个数
注：题型自然是不止这两类，但很大一部分题目都属于这两类，其他的题目要么是非常简单，要么是非常难，要么是变一下形可以变成这两类。
解决方式有：
1.记忆化搜索.
int dp(int i,int b,<判断所需变量>){//i：当前考虑到n的第i位填什么 b:1~i-1位是否“卡上界”
if(i==len+1){return XX;}
if(f[i][j][<判断所需变量>]!=-1)return f[i][j][<判断所需变量>]!=-1;
int sum=0;
for(int d=0;d<=(b?n[i]:9);d++){
sum+=dp(i+1,b&(d==(b?n[i]:9)),<判断所需变量'>);
//可能添加限制条件or something else
}return f[i][j][<判断所需变量>]=sum;
}
“卡上界”的意思是我们填的数跟原数 \(n\) 的这些位完全一致，那么显然下一位要填的数就一定不能超过 \(n\) 的下一位上的数，否则就可以填 \(0\sim 9\)，因此记录是否“卡上界”是非常必要的。
2.顺序 dp.
设 f[i][b][<判断所需变量>] 表示同样的东西，枚举 \(d\)，用它推出 f[i+1][b&(d==(b?n[i]:9))][<判断所需变量>]。
另外，dp 作为一种思维层面的算法，灵活性强，常与其他知识点相结合，如 AC 自动机, etc.
【例1】[ZJOI2010]数字计数
#include
#define int long long
using namespace std;
int 13,n[15],k[2][15],f[15][2][2];
int dp(int q,int i,int b,int h){//h表示是不是1~i-1全都是前导0，如果都是就是0，否则是1
if(i==13+1)return 0;
if(f[i][b][h]!=-1)return f[i][b][h];
int sum=0;
for(int d=0;d<=(b?n[i]:9);d++){
sum+=dp(q,i+1,b&(d==(b?n[i]:9)),h|(d>0));
if(d==q){if(d||h)sum+=k[b&(d==(b?n[i]:9))][i+1];}//如果这一位是要查询的数字(q∈[0,9])那么就会有k[b&(d==(b?n[i]:9))][i+1]个数前面接上d贡献1给答案
//而存在例外就是如果前面都是前导0这里也是0那么这个0就不应该贡献答案
}
return f[i][b][h]=sum;
}
vectorsol(int x){
for(int i=13;i;i--)n[i]=x%10,x/=10;
vectorv;
memset(f,-1,sizeof(f));
int num=0;
for(int i=1;i<=13;i++)num=num*10+n[i];
k[0][13+1]=k[1][13+1]=1;
for(int i=13,j=10;i;i--,j*=10)k[0][i]=k[0][i+1]*10,k[1][i]=1+num%j;
for(int i=0;i<=9;i++){
memset(f,-1,sizeof(f));
v.push_back(dp(i,1,1,0));
}
return v;
}
signed main(){
int a,b;cin>>a>>b;
vectorA=sol(a-1),B=sol(b);
for(int i=0;i<=9;i++)cout<
【例2】[SCOI2009]windy数
属于第1类题型。
#include
using namespace std;
int n[12],f[12][2][10][2];
int dfs(int i,int b,int pre,int u){//u表示是(1)否(0)1~i-1全是前导0，pre表示上一个填的是多少
if(i==11)return 1;
if(f[i][b][pre][u]!=-1)return f[i][b][pre][u];
int sum=0;
for(int d=0;d<=(b?n[i]:9);d++)
if(u||abs(pre-d)>=2)sum+=dfs(i+1,b&(d==(b?n[i]:9)),d,u&!d);//if(u||)的含义：如果全都是前导0的话，这里填什么是没有限制的
return f[i][b][pre][u]=sum;
}
int solve(int x){
for(int y=x,i=10;i;i--,x/=10)n[i]=x%10;
memset(f,-1,sizeof(f));
return dfs(1,1,0,1);
}
int main(){
int a,b;
while(cin>>a>>b){
if(!a&&!b)return 0;
cout<
【例3】萌数
这种“存在……”类型的问题一般容易转化为求满足逆命题的个数再用总数减去之来处理。这题就变成求“不存在长度至少为2的回文子串”。这句话其实非常别扭，而仔细一想就会发现它等价于求每三个相邻数位两两不相等的数的个数。如果你反应不过来，可以有一个突破口：其实每一个奇回文串(len≥3)一定包含一个长恰好3的回文子串，同样每一个偶回文串一定包含一个长恰好为2的回文子串，即两个相邻相等字母。而题目只要“不存在”，所以只看长度2或3的回文串存不存在即可，而这就等价于判断 s[i]!=s[i-1]&&s[i]!=s[i-2]。
#include
using namespace std;
const int mod=1e9+7;
int n[1005],f[1005][2][2][2][10][10];
string l,r;
int dp(int i,int b,int u,int v,int p,int q){
if(i==1001)return 1;
if(f[i][b][u][v][p][q]!=-1)return f[i][b][u][v][p][q];
int sum=0;
for(int d=0;d<=(b?n[i]:9);d++){
if(v||u&&d!=q||!u&&d!=p&&d!=q)sum+=dp(i+1,b&(d==(b?n[i]:9)),v,v&!d,q,d),sum%=mod;
}return f[i][b][u][v][p][q]=sum;
}
string re(string s){
for(int i=0;i=0;i--)k=(k*10ll+a[i]-'0')%mod;//注意ll相关问题
return k;
}
int sol(string s){
memset(f,-1,sizeof(f));
for(int i=1000;i;i--)if((int)s.length()-1001+i>=0)n[i]=s[(int)s.length()-1001+i]-48;else n[i]=0;
return dp(1,1,1,1,0,0);
}
signed main(){
cin>>l>>r;
for(int f=1,i=l.length()-1;i>=0&&f;i--){
int k=l[i]-'0'-f;
if(k<0)k+=10,f=1;
else f=0;
l[i]=k+'0';
}
cout<
【例4】花神的数论题
题型2的模板题。
#include
using namespace std;
const int mod=10000007;
int n[51],f[51][2][51];
int dp(int i,int b,int s){
if(i==51)return max(s,1);//这里是本题的核心，在顺序dp中它表示的就是dp边界;至于为什么要取max(,1)是因为sum(0)=0也会被算到但其实不应该被算
if(f[i][b][s]!=-1)return f[i][b][s];
int sum=1;
for(int d=0;d<=(b?n[i]:1);d++){
sum=1ll*sum*dp(i+1,b&(d==(b?n[i]:1)),s+d)%mod;
}return f[i][b][s]=sum;
}
int main(){
long long x;cin>>x;
memset(f,-1,sizeof(f));
for(int i=50;i;i--,x>>=1)n[i]=x&1;
cout<
【例5】[AHOI2009]同类分布
本题思维难度较以往几题稍有提升，问法也较为灵活。
第一个突破口是能整除原数等价于原数%各位和=0。第二个突破口是实时记录所填数的各位和是不能转移的，而考虑枚举——枚举是简化问题使方便解决的灵活手段。
因此，我们可以记录这样的搜索状态：dp(i,b,k,s)，其中 \(s\) 表示原数各位和，\(k\) 表示原数%\(s\)。
根据【例4】的归纳，我们知道基于各位和问题的核心在于dp边界返回什么值。数位 dp 的边界通常都是 i==len+1，本题就该返回 r==s&&!k（\(r\) 是记录所填数的各位和的变量）。
#include
using namespace std;
typedef long long ll;
int s,n[20];
ll f[20][2][180][180];
ll dp(int i,int b,int k,int r){//k=x%s
if(i==20)return r==s&&!k;
if(f[i][b][k][r]!=-1)return f[i][b][k][r];
ll sum=0;
for(int d=0;d<=(b?n[i]:9);d++)
sum+=dp(i+1,b&(d==(b?n[i]:9)),(10*k+d)%s,r+d);
return f[i][b][k][r]=sum;
}
ll sol(ll x){
for(int i=19;i;i--,x/=10)n[i]=x%10;
ll ans=0;
for(s=1;s<=162;s++){
memset(f,-1,sizeof(f));
ans+=dp(1,1,0,0);
}
return ans;
}
int main(){
ll l,r;
cin>>l>>r;
cout<
【例5】[SDOI2014]数数
前置知识：AC 自动机，数位 DP。
降级版相似题：[JSOI2007]文本生成器
[JSOI2007]文本生成器 题解：
这是一道 AC 自动机上 DP 的题目。AC 自动机上 DP 的基本思路是设 \(f[i][j]\) 表示当前串长 \(i\)、在 \(j\) 号节点。那么本题就可以采用这一思路。设 \(f[i][j]\) 表示当前串长 \(i\)、在 trie 上 \(j\) 号节点，且当前串不包含任何一个单词的方案数。由于在 trie 结构中从某号节点转移到它的子节点比子节点从父节点转移更加便捷，因此考虑用 \(f[i][j]\) 更新 \(f[i+1][trie[j][k]],k\in[0,26)\)。
for(int b=0;b<26;b++)
if(!trie[j][b])(f[i+1][0]+=f[i][j])%=mod;
else if(!cnt[trie[j][b]])(f[i+1][trie[j][b]]+=f[i][j])%=mod;
上面的转移：当该子节点为空时，说明这个子节点对应的字母跟当前串不可能构成单词，因此一定可以接在后面，而后开启“新纪元”（回到 trie 根）。当该子节点不为空时，如果在 AC 自动机上跳着统计完发现不会统计到单词，则可以放，否则放上这个字母就会出现单词而不合法。代码中的 \(cnt\) 为根据 \(fail\) 树预处理出的每个点会统计到的答案。
[JSOI2007]文本生成器 代码
#include
using namespace std;
const int mod=1e4+7;
int n,m,tot,trie[6005][26],fail[6005],f[105][6005],cnt[6005];
string s;
vectorG[6005];
queueQ;
void insert(){
int rt=0;
for(int i=0;i>n>>m;
for(int i=1;i<=n;i++)cin>>s,insert();
get_fail(),sumup(0);
f[0][0]=1;
for(int i=0;i
[SDOI2014]数数 题解：
这道题可以沿用上面 AC 自动机上 DP 的思想，且大同小异。小异在这题有了数位 DP“卡上界”的限制，但其实本质还是上面粗体字的基本思路。
设 \(f_{u,o,i,j}(u,o\in\{0,1\})\) 为状态，\(u,o,i,j\) 的含义见下表：
\(u\)
\(o\)
\(i\)
\(j\)
是(\(1\))否(\(0\))串的 \(1\sim i\) 位置都是前导 0
是(\(1\))否(\(0\))卡上界
当前串长
在 trie 上 \(j\) 号节点
于是：
//t为给定的大数字（字符串），下标从0到m（注意m与原题中不是同一个）
for(int i=0;i
答案即为 \(\sum_{u,o\in\{0,1\},0\le j\le tot}f[u][o][m][j]\)（\(tot\) 表示 trie 中节点最大编号）。
#include
using namespace std;
const int mod=1e9+7;
int n,m,tot,trie[1505][10],fail[1505],f[2][2][1205][1505],cnt[1505],f[1205],p[1205];
string t,s;
vectorf[1505];
queueQ;
void insert(){
int rt=0,l=s.length();
for(int i=0;i>t>>n;m=t.length();
for(int i=1;i<=n;i++)cin>>s,insert();
get_fail(),sumdn(0);
f[1][1][0][0]=1;
for(int i=0;i
【例6】[SDOI2016]储能表
这道题看起来就不是那么数位 dp 了，但发现了数位 dp 可以做之后就比较容易写了（但如果一开始不够仔细就会调两个晚自习）。
考虑 \(i\text{ xor }j\) 则为二进制下数位 dp。所求分为两部分：减 \(k\)+与 0 取 \(\max\)。可以在一次数位 dp 搜索中放两个循环（枚举 \(p,q\)(原题中 \(i,j\))的当前位）。设状态为 dp(i,b1,b2,c)，b1,b2 代表 \(p,q\) 分别是否卡上界。
关于 \(c\) 的解释：从前往后（指从二进制高到低位）观察 \(p\text{ xor }q\) 和 \(k\) 的数位，如果 \(p\text{ xor }q\) 的这一位是大于 \(k\) 的这一位，那么差一定不会小于 0，可以省去与 0 取 \(\max\)，并往后递归，如果后面的位出现 \(p\text{ xor }q\) 小于 \(k\) 的情况则是不需要与 0 取 \(\max\) 的；如果小于，那么差一定小于 0，不往后递归而直接写 0；如果等于则需要继续往后。
类似【例1】，在每一个循环中把 \(((p\text{ xor }q)_i-(k)_i)\cdot M\times 2^{64-i}\)(\(_i\) 表示二进制从高往低第 \(i\) 位值, \(M=\)h[nb1][nb2][i+1] 含义见代码)。
#include
#define int long long
using namespace std;
int n,m,k,p,h[2][2][66],f[66][2][2][2];
int dp(int i,int b1,int b2,int c){
if(i==64)return 0;
if(f[i][b1][b2][c]!=-1)return f[i][b1][b2][c];
int sum=0;
for(int d1=0;d1<=(b1?((n>>(63-i))&1):1);d1++)
for(int d2=0;d2<=(b2?((m>>(63-i))&1):1);d2++){
int nb1=b1&(d1==(b1?((n>>(63-i))&1):1)),nb2=b2&(d2==(b2?((m>>(63-i))&1):1));
if(c||(d1^d2)>=((k>>(63-i))&1))(sum+=dp(i+1,nb1,nb2,c|((d1^d2)>((k>>(63-i))&1))))%=p; //注意这里的 c||，卡了我好久
if(c)(sum+=((1ll<<(63-i))%p*((d1^d2)-((k>>(63-i))&1)+p)%p)%p*h[0][nb1][i+1]%p*h[1][nb2][i+1]%p)%=p;
else (sum+=(1ll<<(63-i))%p*max(0ll,((d1^d2)-((k>>(63-i))&1)))%p*h[0][nb1][i+1]%p*h[1][nb2][i+1]%p)%=p;
}
return f[i][b1][b2][c]=sum;
}
void init(){
scanf("%lld%lld%lld%lld",&n,&m,&k,&p),n--,m--;
h[0][0][64]=h[0][1][64]=h[1][0][64]=h[1][1][64]=1;
for(int i=63;i;i--){
h[0][0][i]=h[0][0][i+1]*2%p;
h[1][0][i]=h[1][0][i+1]*2%p;
}
for(int i=63,j=2;i;j<<=1,i--)h[0][1][i]=(n%j+1)%p; //注意这里和下一排的%p，很重要！
for(int i=63,j=2;i;j<<=1,i--)h[1][1][i]=(m%j+1)%p;
memset(f,-1,sizeof(f));
cout<