专栏文章

数位DP

DDefy_HeavenS
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mindiira
此快照首次捕获于
2025/12/02 00:38
3 个月前
此快照最后确认于
2025/12/02 00:38
3 个月前
查看原文

题目

1081. 度的数量 - AcWing题库 BB 进制下是 0101 串，利用二叉树的结构来考虑（按位分类讨论）。 1082. 数字游戏 - AcWing题库、P2657 [SCOI2009] windy 数 - 洛谷 设 fi,jf_{i,j} 表示长度位 ii，最高位填 jj 的数的个数。 P4127 [AHOI2009] 同类分布 - 洛谷 枚举模数。

P10958 启示录 - 洛谷

题面
对于一个数，若其十进制表示下出现了连续的三个 66，那么它就是魔鬼数。问第 xx 小的魔鬼数，TT 组数据。
1≤T≤1031≤x≤5×107\begin{align} 1\le T\le10^3 \\ 1\le x\le5\times10^7 \end{align}
题解
分析：首先试填法分析问题，确定需要解决的未知信息。那么要解决的未知信息就是，后边有多少种填发能产生魔鬼数？
预处理：设 fi,0/1/2/3f_{i,0/1/2/3} 表示由 ii 位数字构成，开头是 0/1/20/1/2 个 66 的魔鬼数个数，特殊的，fi,3f_{i,3} 表示由 ii 位数字构成的魔鬼数个数。
依次考虑这一位填的数是什么，和填这个数的贡献，可以简单的推出：
fi,0=9×(fi−1,0+fi−1,1+fi−1,2)fi,1=fi−1,0fi,2=fi−1,1fi,3=10×fi−1,3+fi−1,2\begin{align} && f_{i,0}=9\times(f_{i-1,0}+f_{i-1,1}+f_{i-1,2}) \\ && f_{i,1}=f_{i-1,0} \\ && f_{i,2}=f_{i-1,1} \\ && f_{i,3}=10\times f_{i-1,3}+f_{i-1,2} \end{align}
试填：从左到右试填，记录当前末尾连续的 66 的个数。从小到大枚举这一位填什么数，通过 ff 求出这样能得到多少魔鬼数的填发，然后和 xx 做对比，最后一位一位地确定出答案。
CPP
const LL N=20+5;
LL T,n,dp[N][4];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	dp[0][0]=1;
	for(LL i=1;i<=20;i++){
		dp[i][0]=9*(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]);
		dp[i][1]=dp[i-1][0];
		dp[i][2]=dp[i-1][1];
		dp[i][3]=10*dp[i-1][3]+dp[i-1][2];
	}
	cin>>T;
	while(T--){
		cin>>n;
		LL len=3;
		while(dp[len][3]<n){
			len++;
		}
		for(LL i=len,k=0;i>=1;i--){
			for(LL j=0,cnt;j<=9;j++){
				cnt=dp[i-1][3];
				if(j==6||k==3){
					for(LL l=max(3-k-(j==6),0ll);l<=2;l++){
						cnt+=dp[i-1][l];
					}
				}
				if(cnt<n){
					n-=cnt;
				}else{
					if(k<3){
						if(j==6){
							k++;
						}else{
							k=0;
						}
					}
					cout<<j;
					break;
				}
			}
		}
		cout<<"\n";
	}
	return 0;
}

P10959 月之谜 - 洛谷

题面
对于一个数，若它能被自己地数位和整除，那么它就是月之数。问区间 [l,r][l,r] 内有多少月之数，多组数据。
1≤l,r<232数据组数≤3×103\begin{align} 1\le l,r<2^{32} \\ 数据组数\le3\times10^3 \end{align}
题解
分析：如果设 g(l,r)g(l,r) 表示区间 [l,r][l,r] 内地月之数个数，那么 g(l,r)=g(1,r)−g(1,l−1)g(l,r)=g(1,r)-g(1,l-1) 或 g(l,r)=g(0,r)−g(0,l−1)g(l,r)=g(0,r)-g(0,l-1)。那么问题就可以统一成求 g(1,x)g(1,x)。
试填法分析一下，假设目前是 a1a2a3a4a5a6‾\overline{a_1a_2a_3a_4a_5a_6}（a1,a2,a3a_1,a_2,a_3 已知），设 (a1×105+a2×104+a3×103) mod ∑a=p(a_1\times 10^5+a_2\times 10^4+a_3\times 10^3)\bmod\sum_a=p，那么只有 (a4×102+a5×10+a6) mod ∑a=∑a−p(a_4\times 10^2+a_5\times 10+a_6)\bmod\sum_a=\sum_a-p 才能满足条件。
这个题中，模数不是固定的，是随数字的变化而变化，不好 DP，所以直接枚举模数，在本题就是各位数字之和。
也就是说，一些会随着要统计的东西变化而变化的东西，如果不好处理，又不是很大，可以考虑在外层枚举。
枚举模数，或者说数字之和 sumsum。试填中，记录数字目前填出来的这几位数对 sumsum 取模的余数 ww 和目前地数字和 ss（目前填出来的这几位数指的是高位的数，可以理解为后面低位的数都是 00），然后后面要求的未知信息就是，对 sumsum 取模的余数为 sum−wsum-w 且数字之和为 sum−ssum-s 的数的个数。
预处理：设 fi,j,k,mf_{i,j,k,m} 表示 ii 位数字，各位数字之和为 jj，对 kk 取模的余数为 mm 的数的个数。
考虑这一位填什么可以推出：
fi,j,k,m=∑q=09fi−1,j−q,k,(m−q×10i−1) mod kf_{i,j,k,m}=\sum_{q=0}^{9}f_{i-1,j-q,k,(m-q\times 10^{i-1})\bmod k}
试填：从左往右依次考虑每个数位，仍记录上文中说的 sum,w,ssum,w,s，若第 ii 位填 aa：
  1. a<xia<x_i，后面可以随便填，也就是 fi−1,sum−a−s,sum,(sum−w−a×10i−1) mod sumf_{i-1,sum-a-s,sum,(sum-w-a\times10^{i-1})\bmod sum}；
  2. a=xia=x_i，这样后面就会收到限制（其实，如果考虑这种情况，那么 i+1i+1 位一定也是这种情况，否则不会收到限制），更新 w,sw,s，交给下一位去做。
然后试填出答案。
CPP
const LL N=90+1;
LL l,r,pw[11],dp[11][N][N][N];

LL get(LL x){
	if(!x) return 0;
	LL tmp=x,sum=0,res;
	vector<LL>num;
	while(tmp){
		num.pb(tmp%10);
		sum+=tmp%10;
		tmp/=10;
	}
	res=(x%sum==0);
	for(LL s=1,sum,now;s<=90;s++){
		sum=s,now=0;
		for(LL i=num.size();i>=1;i--){
			for(LL val=0;val<=min(num[i-1]-1,sum);val++){
				res+=dp[i-1][sum-val][s][(s-(now+val*pw[i-1]%s)%s+s)%s];
			}
			sum-=num[i-1];
			if(sum<0){
				break;
			}
			(now+=num[i-1]*pw[i-1]%s)%=s;
		}
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	pw[0]=1;
	for(LL i=1;i<=10;i++){
		pw[i]=pw[i-1]*10;
	}
	for(LL i=1;i<=90;i++){
		dp[0][0][i][0]=1;
	}
	for(LL i=1;i<=10;i++){
		for(LL j=0;j<=90;j++){
			for(LL k=1;k<=90;k++){
				for(LL m=0;m<k;m++){
					for(LL val=0;val<=min(9ll,j);val++){
						dp[i][j][k][m]+=dp[i-1][j-val][k][(m-val*pw[i-1]%k+k)%k];
					}
				}
			}
		}
	}
	while(cin>>l>>r){
		cout<<get(r)-get(l-1)<<"\n";
	}
	return 0;
}

P6218 [USACO06NOV] Round Numbers S - 洛谷

题面
对于一个数，若其二进制表示下 00 的个数不小于 11 的个数，那么这个数就是圆数。问区间 [l,r][l,r] 内有多少个圆数。
1≤l,r≤2×1091\le l,r\le 2\times 10^9
题解
分析：二进制下的试填法分析，发现要 DP 的是有 ii 位且 00 的个数为 kk 的数的个数。但是这里的前导零会影响到 00 的个数，从而影响正确性，所以需要再记录一个 jj 表示最高位填什么，试填的时候也要把前导零特殊考虑一下。
预处理：设 fi,j,kf_{i,j,k} 表示二进制下有 ii 位，最高位填 jj，00 的个数位 kk 的数的个数。
fi,0,k=fi−1,0,k−1+fi−1,1,k−1fi,1,k=fi−1,0,k+fi−1,1,k\begin{align} && f_{i,0,k}=f_{i-1,0,k-1}+f_{i-1,1,k-1} \\ && f_{i,1,k}=f_{i-1,0,k}+f_{i-1,1,k} \end{align}
试填：要求 [0,x][0,x] 之间的圆数个数，分成两种数（xx 在二进制下位数为 mm）：
  1. 二进制位数小于 mm；
  2. 二进制位数等于 mm；
对于第一种数，枚举位数 <m<m，枚举合法的 00 的数量（或 11 的数量），用 ff 求数量。
对于第二种数，从左到右枚举每一位，记录前面 00 的个数，遇到 xx 这一位是 11，就枚举后面合法的 00 的个数（或 11 的个数），用 ff 求数量。
CPP
const LL N=32+5;
LL l,r,dp[N][2][N];

LL get(LL x){
	if(!x) return 1;
	LL tmp=x,res=1;
	vector<LL>a;
	while(tmp){
		a.pb(tmp&1);
		tmp>>=1;
	}
	for(LL i=1;i<a.size();i++){  //数位个数比x小的 
		for(LL j=0;j<=i/2;j++){
			res+=dp[i][1][i-j];
		}
	}
	for(LL i=a.size()-2,cnt=0,val;~i;i--){  //数位个数和x一样的 
		val=a[i];
		if(val){
			for(LL k=0;k<=a.size();k++){
				if(k+cnt>=a.size()-(k+cnt)){
					res+=dp[i+1][0][k];
				}
			}
		}
		if(!val) cnt++;
		if(!i&&cnt>=a.size()-cnt) res++;
	}
	return res;
}
LL fac[N];
void init(LL n){
	fac[0]=1;
	for(LL i=1;i<=n;i++){
		fac[i]=fac[i-1]*i;
	}
}
LL C(LL n,LL m){
	if(n<m) return 0;
	return fac[n]/fac[n-m]/fac[m];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>l>>r;
	init(31);
	dp[1][0][1]=1,dp[1][1][0]=1;
	for(LL i=2;i<=32;i++){
		for(LL j=0;j<=i;j++){
			if(j) dp[i][0][j]=dp[i-1][0][j-1]+dp[i-1][1][j-1];
			dp[i][1][j]=dp[i-1][0][j]+dp[i-1][1][j];
		}
	}
	cout<<get(r)-get(l-1);
	return 0;
}

1086. 恨7不成妻 - AcWing题库

全场 MVP
题面
对于一个数，如果满足一下任意一种情况，那么它就是一个与 77 相关的数：
  • 十进制表示下，数位上有 77；
  • 十进制下，数位和是 77 的倍数；
  • 这数是 77 的倍数。
求区间 [l,r][l,r] 内与 77 无关的数的数位和，TT 组数据。
1≤T≤501≤l≤r≤1018\begin{align} 1\le T\le50 1\le l\le r\le10^{18} \end{align}
题解
分析：与前几题不一样的是，它求的不是数的数量，而是平方和。
仍然试填法，考虑当第 ii 位填 jj 时的与 77 无关的数的平方和，假设 i−1i-1 位的数字中与 77 无关的数有 mm 个，分别是 A1,A2,…,AmA_1,A_2,\dots,A_m。那么第 ii 位填 jj 的数的平方和就是 ∑k=1m(j×10i−1+Ak)2=m×(j×10i−1)2+2×j×10i−1×(∑k=1mAk)+∑k=1mAk2\sum_{k=1}^{m}(j\times 10^{i-1}+A_k)^2=m\times(j\times 10^{i-1})^2+2\times j\times10^{i-1}\times(\sum_{k=1}^{m}A_k)+\sum_{k=1}^{m}A_k^2。
预处理：现在问题就分成了三个子问题 m×(j×10i−1)2m\times(j\times 10^{i-1})^2、2×j×10i−1×(∑k=1mAk)2\times j\times10^{i-1}\times(\sum_{k=1}^{m}A_k) 和 ∑k=1mAk2\sum_{k=1}^{m}A_k^2。
对于第一个子问题 m×(j×10i−1)2m\times(j\times 10^{i-1})^2，i,ji,j 都是枚举的，唯一要求的就是 mm，也就是 i−1i-1 位的数字中与 77 无关的数的数量。所以设 fi,j,a,bf_{i,j,a,b} 表示有 ii 位，最高位填 jj，数位和模 77 的余数为 aa，数本身模 77 的余数为 bb 的数的数量。
设 x=(((a−j) mod 7)+7) mod 7x=(((a-j)\bmod7)+7)\bmod7 为 i−1i-1 位数的数位和模 77 的余数（i−1i-1 位数的 aa），y=(((b−j×10i−1) mod 7)+7) mod 7y=(((b-j\times 10^{i-1})\bmod7)+7)\bmod7 为 i−1i-1 位数模 77 的余数（i−1i-1 位数的 bb）。那么 m=∑0≤p≤9,p≠7fi−1,p,x,ym=\sum_{0\le p\le9,p\ne7}f_{i-1,p,x,y}。
推转移式，考虑下一位填什么。
fi,j,a,b=∑0≤p≤9,p≠7fi−1,p,x,yf_{i,j,a,b}=\sum_{0\le p\le9,p\ne7}f_{i-1,p,x,y}
对于第二个子问题 2×j×10i−1×(∑k=1mAk)2\times j\times10^{i-1}\times(\sum_{k=1}^{m}A_k)，主要是 ∑k=1mAk\sum_{k=1}^{m}A_k 难求，即 i−1i-1 位的数字中与 77 无关的数的和。所以设 hi,j,a,bh_{i,j,a,b} 表示有 ii 位，最高位填 jj，数位和模 77 的余数为 aa，数本身模 77 的余数为 bb 的数的和。
仍然计算刚才的 x,yx,y。那么 ∑k=1mAk=∑0≤p≤9,p≠7hi−1,p,x,y\sum_{k=1}^{m}A_k=\sum_{0\le p\le9,p\ne7}h_{i-1,p,x,y}。
对于满足 hi,j,a,bh_{i,j,a,b} 条件的 tt 个数 B1,B2,…,BtB_1,B_2,\dots,B_t，因为最高位填的都是 jj，所以 hi,j,a,b=∑k=1tBk=∑k=1t(j×10i−1+Ck)=t×j×10i−1+∑k=1tCkh_{i,j,a,b}=\sum_{k=1}^{t}B_k=\sum_{k=1}^{t}(j\times10^{i-1}+C_k)=t\times j\times10^{i-1}+\sum_{k=1}^{t}C_k，其中 CC 是 i−1i-1 位的合法的数（前面计算的 x,yx,y 就是保证它合法的），所以 ∑k=1tCk=∑0≤p≤9,p≠7hi−1,p,x,y\sum_{k=1}^{t}C_k=\sum_{0\le p\le9,p\ne7}h_{i-1,p,x,y}。而 tt 有是刚才我们求出的 ∑0≤p≤9,p≠7fi−1,p,x,y\sum_{0\le p\le9,p\ne7}f_{i-1,p,x,y}。发现都有 ∑0≤p≤9,p≠7\sum_{0\le p\le9,p\ne7} 的一个求和，直接把它提到最前面。
hi,j,a,b=∑0≤p≤9,p≠7(fi−1,p,x,y×j×10i−1+hi−1,p,x,y)h_{i,j,a,b}=\sum_{0\le p\le9,p\ne7}(f_{i-1,p,x,y}\times j\times10^{i-1}+h_{i-1,p,x,y})
对于第三个子问题 ∑k=1mAk2\sum_{k=1}^{m}A_k^2，i−1i-1 位的数字中与 77 无关的数的平方和。设 gi,j,a,bg_{i,j,a,b} 表示有 ii 位，最高位填 jj，数位和模 77 的余数为 aa，数本身模 77 的余数为 bb 的数的平方和。
x,yx,y 还是刚才那个定义和计算方法。那么 ∑k=1mAk2=∑0≤p≤9,p≠7gi−1,p,x,y\sum_{k=1}^{m}A_k^2=\sum_{0\le p\le9,p\ne7}g_{i-1,p,x,y}。
对于转移，发现这不就是原本问题“第 ii 位填 jj 时的与 77 无关的数的平方和”，再加上两个限制啊！刚才的 m=∑0≤p≤9,p≠7fi−1,p,x,ym=\sum_{0\le p\le9,p\ne7}f_{i-1,p,x,y}、∑k=1mAk=∑0≤p≤9,p≠7hi−1,p,x,y\sum_{k=1}^{m}A_k=\sum_{0\le p\le9,p\ne7}h_{i-1,p,x,y} 和 ∑k=1mAk2=∑0≤p≤9,p≠7gi−1,p,x,y\sum_{k=1}^{m}A_k^2=\sum_{0\le p\le9,p\ne7}g_{i-1,p,x,y} 都有一个枚举这一位填的数 pp 的求和，把它提到最前面。
gi,j,a,b=∑0≤p≤9,p≠7(fi−1,p,x,y×(j×10i−1)2+2×j×10i−1×hi−1,p,x,y+gi−1,p,x,y)g_{i,j,a,b}=\sum_{0\le p\le9,p\ne7}(f_{i-1,p,x,y}\times(j\times10^{i-1})^2+2\times j\times10^{i-1}\times h_{i-1,p,x,y}+g_{i-1,p,x,y})
试填：从左到右，记录数位和和前几位数字，根据试填法和上文分析的“第 ii 位填 jj 的数的平方和就是 ∑k=1m(j×10i−1+Ak)2=m×(j×10i−1)2+2×j×10i−1×(∑k=1mAk)+∑k=1mAk2\sum_{k=1}^{m}(j\times 10^{i-1}+A_k)^2=m\times(j\times 10^{i-1})^2+2\times j\times10^{i-1}\times(\sum_{k=1}^{m}A_k)+\sum_{k=1}^{m}A_k^2。”就可以求出答案了。
CPP
#include<bits/stdc++.h>
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define tmax(a,b) (a)=max((a),(b))
#define tmin(a,b) (a)=min((a),(b))

using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;

const LL N=19+5,M=10+5,Mod=1e9+7;
LL l,r,pw1[N],pw2[N],f[N][M][M][M],g[N][M][M][M],h[N][M][M][M];

LL get(LL x){
	if(!x){
		return 0;
	}
	LL tmp=x,res=0;
	vector<LL>arr;
	while(tmp){
		arr.pb(tmp%10);
		tmp/=10;
	}
	for(LL i=arr.size()-1,sum=0,num=0,val;~i;i--){
		val=arr[i];
		for(LL j=0;j<val;j++){
			if(j==7) continue;
			for(LL a=0;a<=6;a++){
				if((sum+a)%7==0) continue;
				for(LL b=0;b<=6;b++){
					if((num%7*pw1[i+1]+b)%7==0) continue;
					(res+=(((num%Mod*pw2[i+1]%Mod)*(num%Mod*pw2[i+1]%Mod)%Mod*f[i+1][j][a][b]%Mod
					+2*num%Mod*pw2[i+1]%Mod*h[i+1][j][a][b]%Mod)%Mod
					+g[i+1][j][a][b])%Mod)%=Mod;
				}
			}
		}
		if(val==7){
			break;
		}
		sum+=val,num=num*10+val;
		if(!i&&sum%7&&num%7){
			(res+=x%Mod*(x%Mod)%Mod)%=Mod;
		}
	}
	return res;
}

void solve(){
	cin>>l>>r;
	cout<<((get(r)-get(l-1))%Mod+Mod)%Mod<<"\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	pw1[0]=pw2[0]=1;
	for(LL i=1;i<=20;i++){
		pw1[i]=pw1[i-1]*10%7,pw2[i]=pw2[i-1]*10%Mod;
	}
	for(LL i=0;i<=9;i++){
		if(i==7) continue;
		f[1][i][i%7][i%7]++;
		h[1][i][i%7][i%7]+=i;
		g[1][i][i%7][i%7]+=i*i;
	}
	for(LL i=2;i<=19;i++){
		for(LL j=0;j<=9;j++){
			if(j==7) continue;
			for(LL a=0;a<=6;a++){
				for(LL b=0,x,y;b<=6;b++){
					x=((a-j)%7+7)%7,y=((b-j*pw1[i-1])%7+7)%7;
					for(LL k=0;k<=9;k++){
						if(k==7) continue;
						(f[i][j][a][b]+=f[i-1][k][x][y])%=Mod;
						(h[i][j][a][b]+=(j*pw2[i-1]%Mod*f[i-1][k][x][y]%Mod+h[i-1][k][x][y])%Mod)%=Mod;
						(g[i][j][a][b]+=(((j*pw2[i-1]%Mod)*(j*pw2[i-1]%Mod)%Mod*f[i-1][k][x][y]%Mod+2*j*pw2[i-1]%Mod*h[i-1][k][x][y]%Mod)%Mod+g[i-1][k][x][y])%Mod)%=Mod;
					}
				}
			}
		}
	}
	LL t=1;cin>>t;
	while(t--) solve();
	return 0;
}
/* 
有两个模数，不要随意取模，有可能另一个模数也需要用到这个变量！！ 
*/

套路

一般有两种类型的题：
  1. 满足条件的第 kk 小的数？
  2. 区间 [l,r][l,r] 内有多少满足条件的数？
一个重要的方法——试填法，就是从高位到低位一次去试着填数，对于每一位，分析填入某个数带来的贡献。假如现在填到了第 ii 位，那么前面的高位都确定了，可以记录一些值，后面的低位是不确定的，需要预处理 DP 来求出合法的数的数量。
  1. 对于第一种题，试填到第 ii 位，前面的高位就是已经确定的答案，枚举第 ii 位填的数 aa，和填 aa 时后面低位合法的填发的数量，然后通过这个数量求出填 aa 的最大数的排名，确定第 kk 小的这个数第 ii 位填的是什么。
  2. 对于第二种题，用前缀和的思想，把 [l,r][l,r] 拆成 [1,r]−[1,l−1][1,r]-[1,l-1] 或 [0,r]−[0,l−1][0,r]-[0,l-1]，问题被统一成求 [1,x][1,x] 内的数量。试填到第 ii 位，前面的高位就是 xx 的数位，枚举第 ii 位填的数 a<xia<x_i，通过预处理的 DP 求出后面低位合法的填发的数量，对于 a=xia=x_i，后面低位填什么就会被限制（为了使数 ≤x\le x），所以交给下一位去做，这样刚好满足上文所说的“前面的高位就是 xx 的数位”。
首先用试填法分析题目，分析出需要用 DP 预处理出什么东西，来求合法的数的个数。然后 DP，DP 的格式一般为 fi(,j),…f_{i(,j),\dots} 表示有 ii 位，有些题目要记录最高位填的数为 jj，…\dots 就是要额外记录的信息。这里 DP 出的数是存在前导零的，所以试填求区间 [1/0,x][1/0,x] 的过程中不用特殊考虑那些数位比 xx 数位小的数，直接把前导零看作是空就行，也不用特殊考虑填到中间，需要填一些 00，直接用预处理的 DP 求出填发的数量就行。但又有特例，如果整个数的前导零会影响正确性（也就是说，不能把前导零看作是空），那么需要特殊考虑数位比 xx 数位小的数。最后试填求出答案。
对于那种求数字和、平方和的也一样，就是分析的时候要转换一下，多处理几个 DP。
要为了试填而 DP，而不是先想 DP 再试填。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...