数位DP

字数统计: 4.9k   |   阅读时长≈ 22 分钟

数位DP

0. 概述

  • 数位$DP$的特点：求某个区间 $[L,R]$，满足某种性质的数的个数

  • 数位$DP$的技巧 $1$：类似前缀和的思想，转换为 $[0,R]-[0,L-1]$ 求解

  • 数位$DP$的技巧 $2$：从高位到低位填数字，要分类讨论。把整数 $R$ 的每一位取出来，存入数组 $a$，则 $R=a_na_{n-1}a_{n-2}…a_1$从高位到低位填数，划分两类：$[0,a_i-1]$ 和 $a_i$，如果 $i$ 位填 $[0,a_i-1]$ 则后面每一位都可以填 $[0,9]$；如果 $i$ 位填 $a_i$，则再讨论下一位，这样就可以保证填的数不超过 $R$

  • 若 $R=235$，从高位到低位所以先看第一位百位 $a_i=2$，此时第一位可以填 $[0,a_i-1]$ 也就是 $[0,1]$，当 $a_i$ 填 $[0,1]$ 时剩下的每一位都可以填 $[0,9]$，故有 $[000,099]$ 和 $[100,199]$，这些数字都小于 $R$；当 $a_i$ 填 $2$ 时，进而开始看十位 $ai=3$，此时第二位可以填 $[0,a_i-1]$ 也就是 $[0,2]$，当第二位填 $[0,2]$ 时剩下每一位都能填 $[0,9]$ 故有 $[200,209]$，$[210,219]$，$[220,229]$，当 $a_i$ 填 $3$ 时就要进而讨论最后一位个位 $a_i=5$；此时也要分个位 $a_i$ 取 $[0,4]$ 和 $5$，这样就得到了 $<=R$ 的数集进行了划分

image-20240504112310985

  • 代码模板
    • 先对数集从低位到高位做预处理
    • 再对数据从高位到低位做递推

1. 数字游戏

推荐学习视频：E36 数位DP 数字游戏_bilibili
题目描述：从左往右各数字呈非下降关系如 $123$,$446$，问给定区间 $[a,b]$ 求区间内不降数的个数

  • 不降数的个数应该与位数和最高位的数字有关
  • 状态表示：$f[i,j]$ 表示一共有 $i$ 位，且最高位数字为 $j$ 的不降数的个数
  • 状态转移：$f[i,j]=f[i-1,j]+f[i-1,j+1]+f[i-1,j+2]+…+f[i-1,9]$ ，因为最高位固定为 $j$，所以假设第 $i-1$ 位是 $k$，根据不降数的定义 $k>=j$，故有 $f[i,j]=\sum_{k=j}^9\ f[i-1,k]$，一位一位的确定，所以 $f[i]$ 由 $f[i-1]$ 转移过来。举个比较简单的例子，$f[3,5]$ 表示三位数，最高位数字为 $5$，那么它应该是由 $f[2,5]+f[2,6]+…+f[2,9]$ 转移得到的，比如 $f[2,5]$ 就应该是 $f[1,5]+f[1,6]+…+f[1,9]$ 转移得到的
  • 边界初值：$f[1,i]=1\ (i=[1,9])$ 只有一位数时不降数为 $1$

1.1. 完整代码

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
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

// a<=b<=2^31-1≈2.1×10^9,所以不超过10位数
const int N=12; // 略开大一点,以防万一
int a[N]; // 保存数字的每一位
int f[N][N]; // f[i][j]:一共有i位且最高位数字是j的不降数的个数

// 预处理不降数的个数
void init() {
	for(int i=0;i<=9;i++) f[1][i]=1; // 所有1位数,不降数个数为1
	// 1) 枚举位数,刚才计算了一位数,这里从两位数算起走
	for(int i=2;i<N;i++) {
		// 2) 枚举最高位
		for(int j=0;j<=9;j++) {
			// 3) 枚举次高位,k>=j,满足不降数的条件
			for(int k=j;k<=9;k++) {
				// 累加方案数
				f[i][j]+=f[i-1][k];
				printf("f[%d %d]=%d\n",i,j,f[i][j]);
			}
		}
	} 
}

// 计算[0,n]有多少个不降数,从高位到低位进行枚举统计,时间按复杂度是10
int dp(int n) {
	if(!n) return 1; // 特判,n=0也是一种不降数,返回1
	int cnt=0;
	while(n) a[++cnt]=n%10,n/=10; // 取位运算
	int res=0,last=0; // res:答案,last:保存上一位数字
	// 从高位到低位枚举每个数字
	for(int i=cnt;i>=1;i--) {
		int now=a[i]; // 当前位数字
		// 枚举当前位可以填入的数字,不能小于last,保证填的数不超过传入的数n
		for(int j=last;j<now;j++) {
			res+=f[i][j];
			printf("当前枚举到第i=%d位, f[%d %d]=%d res=%d\n",i,i,j,f[i][j],res);
		}
		if(now<last) break; // 比如遇到528,5过后是2,now<last了,就直接break,后面不用算 
		last=now; // 更新上一位的数字
		if(i==1) res++; // 走到各位上的最后一次拆分且没有break出去,说明本身是一个不降数,ans++
	}
	return res;
}

int main() {
	init(); // 预处理不降数个数
	int l,r;
	while(cin>>l>>r) {
		cout<<dp(r)-dp(l-1)<<endl;
	}
	return 0;
}

1.2. 样例解析

  • 统计 $[1,2557]$ 的不降数个数，对 $2557$ 进行拆分存储到 $a$ 数组中，从高位到低位依次枚举数字 $2,5,5,7$。
    • 当枚举到最高位 $2$ 时，$last=0$，则最高位可以取 $[0,1]$，$res+=f[4,0]+f[4,1]$；
    • 当枚举到下一位 $5$ 时，$last=2$（更新，满足不降数），则这一位可取 $[2,4]$，$res+=f[3,2]+f[3,3]+f[3,4]$
    • 当枚举到下一位 $5$ 时，$last=5$，$last<now$ 中没有可取元素，故跳过
    • 当枚举到最后一位 $7$ 时，$last=5$，故这一位可取 $[5,6]$，$res+=f[2,5]+f[2,6]$，枚举到最后一位都没有退出，说明 $n=2557$ 本身也为一个不降数，故 $res+=1$
  • 统计 $[1,1]$ 的不降数个数，就是 $1$，所以 $res=1$
  • 二者做差，最终结果为 $472$

image-20240504133801132

  • 统计 $[1,5728]$ 的不降数个数，对 $5728$ 进行拆分存储到 $a$ 数组中，从高位到低位依次枚举数字 $5,7,2,8$。
    • 当枚举到最高位 $5$ 时，$last=0$，则最高位可以取 $[0,4]$，$res+=f[4,0]+f[4,1]+f[4,2]+f[4,3]+f[4,4]$；
    • 当枚举到下一位 $7$ 时，$last=5$（更新，满足不降数），则这一位可取 $[5,6]$，$res+=f[3,5]+f[3,6]$
    • 当枚举到下一位 $2$ 时，$last=7$，$last>now$ 不满足不降数，直接 $break$
  • 统计 $[1,1]$ 的不降数个数，就是 $1$，所以 $res=1$
  • 二者做差，最终结果为 $669$

image-20240504134452689

2. Windy数

推荐学习视频：E37 数位DP Windy数_bilibili
求区间 $[a,b]$ 中不含前导 $0$ 且相邻两个数字之差至少为 $2$ 的正整数（$Windy$ 数）个数

  • 注意，个位数都是 $Windy$ 数，并且 $Windy$ 数不含前导 $0$，而上一题中是可以包含前导 $0$ 的，毕竟在最高位补 $0$ 并不影响这个数字是否为不降数，因为 $0$ 始终是最小的

  • 状态表示：$f[i,j]$ 表示一共有 $i$ 位，且最高位数字为 $j$ 的 $Windy$ 数的个数

  • 分段统计（思路）：同样的，用 $last$ 记录上一位数字，枚举当前位 $j$，如果 $abs(j-last)>=2$ （成为 $Windy$ 数条件）就累加答案，$res+=f[i,j]$；前面的答案都是 $n$ 位的，对于位数低于 $n$ 位的，再分段统计，累加到答案中即可，例如：$[100,999]$、$[10,99]$、$[1,9]$

  • 本题在使用数位$DP$的技巧时需要注意：因为不存在前导 $0$，所以最高位只能补 $[1,a_1-1]$，而其他位是 $[0,a_i-1]$

image-20240504203750057

2.1. 完整代码

  • 代码需要注意几个地方，因为不含前导 $0$，所以从高位到低位处理
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=12; // INT_MAX=2×10^9,稍微多开一点空间
int a[N]; // 每一位存进a
int f[N][10]; // f[i][j]:一共有i位,最高位为j的Windy数的个数

// 预处理出所有Windy数,时间复杂度1000
void init() {
	for(int i=0;i<=9;i++) {
		f[1][i]=1; // 一位数均为Windy数,包括0	
		printf("f[%d %d]=%d\n",1,i,f[1][i]);
	}
	// 1) 枚举位数(从2位数开始)
	for(int i=2;i<N;i++) {
		// 2) 枚举第i位
		for(int j=0;j<=9;j++) {
			// 3) 枚举第i-1位
			for(int k=0;k<=9;k++) {
				// 如果满足Windy数条件,则转移
				if(abs(k-j)>=2) { // 求出所有k-j>=2和j-k>=2的情况
					f[i][j]+=f[i-1][k]; 	
					printf("f[%d %d]=%d\n",i,j,f[i][j]);
				}
			}
		}
	}
}

// 求1~x的所有Windy数的个数
// 注意,数位DP时一定保证枚举到的数不超过x本身
int dp(int x) {
	if(!x) return 0; // 特判,如果x==0返回0
	int cnt=0;
	while(x) a[++cnt]=x%10,x/=10; // 将x拆位存进数组a
	// 1) 答案是cnt位的情况,那么最高位的取值范围是[1,now-1],如r=1234
	int res=0,last=-2; // last取一个≤-1的值即可,只要保证j-last>=2
	// 从最高位到低位枚举
	for(int i=cnt;i>=1;i--) {
		int now=a[i]; // 取出当前位数字
		// 最高位从1开始,此时i==cnt,不是最高位就从0开始
		for(int j=(i==cnt);j<now;j++) {
			if(abs(j-last)>=2) {
				res+=f[i][j];
				printf("i=%d f[%d %d]=%d res=%d\n",i,i,j,f[i][j],res);
				cout<<now<<' '<<last<<endl;
			}
		}
		// 不满足定义直接break掉
		if(abs(now-last)<2) break;
		last=now; 
		if(i==1) {
			res++; // 能走到a1说明x本身是Windy数故+1
			printf("i=%d res=%d (走到a1)\n",i,res);
		}
	}
	cout<<"以下是答案小于cnt位的情况"<<endl;
	// 2) 答案小于cnt位,如r=1234时,对234
	for(int i=1;i<cnt;i++) {
		for(int j=1;j<=9;j++) {
			res+=f[i][j];
			printf("i=%d f[%d %d]=%d res=%d\n",i,i,j,f[i][j],res);
		}
	}
	printf("res=%d (加上小于n位的后)\n",res);
	return res;
}


int main() {
	init();
	int l,r;
	cin>>l>>r;
	cout<<dp(r)-dp(l-1);
	return 0;
}

2.2. 样例解析

  • 求区间 $[1,345]$ 中的 $Windy$ 数，则 $cnt==3$
    • 当答案为 $3$ 位时 $(cnt)$
      • 当枚举到最高位 $now=a_i=3$ 时，$last=-2$，进入 $for$ 循环，最高位能取 $[1,2]$（注意因为不含前导 $0$，最高位只能从 $1$ 开始枚举），故 $res+=f[3,1]+f[3,2]$，此时 $now-last>=2$ 故不用退出计算，继续看下一位
      • 当枚举到下一位 $now=a_i=4$ 时，$last=3$，进入 $for$ 循环，这一位能取 $[0,2]$（不是最高位，可以从 $0$ 开始取），但是当 $a_i=2$ 时不满足 $last-a_i>=2$，所以 $res+=f[2,0]+f[2,1]$，不加 $f[2,2]$，此时 $now-last<2$ 了不满足约束条件，所以直接剪枝退出循环
    • 当答案小于 $3$ 位时，这一步是对上一种情况没枚举完的进行枚举，$345$ 是 $3$ 位数，$<cnt$ 的第一个数是 $cnt-1=2$，故枚举累加 $[\ f[1,1],\ f[2,9]\ ]$，即 $[1,99]$

image-20240505094618965

  • 求区间 $[1,2572]$ 中的 $Windy$ 数，可以自己模拟一下，这里不做阐释

image-20240505100100091

3. 度的数量

推荐学习视频：E38 数位DP 度的数量_bilibili
求区间 $[X,Y]$ 中满足恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和的数的统计个数

  • $K$ 个互不相等的 $B$ 的整数次幂，等价于是求 $[X,Y]$ 中有多少个数字在 $B$ 进制表示法下由 $K$ 个 $1$ 组成，其余位都是 $0$

image-20240506092242964

3.1. 状态预处理

  • 状态表示 $f[i,j]$：表示 $i$ 个位置上出现 $j$ 个 $1$ 的组合数，如 $f[4,2]$ 表示 $4$ 位上出现 $2$ 个 $1$ 的组合数，很显然情况有：$0011,\ 0101,\ 1001,\ 1010,\ 1100,\ 0110$，就是组合数学中的 $c_4^2=6$
  • 状态转移 $f[i,j]=f[i-1,j-1]+f[i-1,j]$ ：从 $i$ 个数中选 $j$ 个数，分两类，对于第 $1$ 个数选或不选，如果选，则从剩余的 $i-1$ 个数中再选 $j-1$ 个，即 $c_{i-1}^{j-1}$；如果不选，则从剩下 $i-1$ 个数中再选 $j$ 个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N=34; // INT_MAX大约2×10^10,转换成2进制最多2^31,为了保险稍开大一点
int a[N];
int f[N][N]; // f[i][j]:表示i个位置上放置j个1的组合数,如C42=6,则f[4][2]=6
int K,B; // b进制表示,k个1

// 预处理组合数
void init() {
	for(int i=0;i<N;i++) f[i][0]=1; // Cn0=1,cnn的0在下方的递推式中可以得到为1
	for(int i=1;i<N;i++) {
		for(int j=1;j<=i;j++) {
			f[i][j]=f[i-1][j-1]+f[i-1][j]; // 组合数计算公式
			// c(i)(j)=c(i-1)(j-1)+c(i-1)(j)
		}
	}
}

3.2. 状态转移

  • 把数字 $n$ 转化为 $B$ 进制数，随后从高位向低位枚举，假设枚举到第 $i$ 位，第 $i$ 位上的数字的 $x$，$last$ 记录第 $i$ 位之前放置 $1$ 的个数， 则分以下情况讨论
  1. $x==0$：直接跳过，继续枚举下一位
  2. $x==1$：第 $i$ 位再分为两种情况
    1. 第 $i$ 位放 $0$，后面 $i-1$ 位上可以放 $k-last$ 个 $1$，$res+=f[i-1][k-last]$
    2. 第 $i$ 为放 $1$，后面 $i-1$ 位上的情况不能用组合数计算，因为要保证答案中的数字比原数字小，所以固定第 $i$ 位为 $1$，继续枚举下一位

image-20240506201634106

  • 比如当 $n=65$ 时，转换成 $B=4$ 进制数后为 $1001$，从最高位开始枚举，如果 $a_n$ 放 $0$，那么后面的每一位都可以取 $[0,B-1]$ 即 $[0,3]$，故有 $[0000,0333]$，因为 $K=2$，而 $a_n$ 为 $0$，所以需要让后 $3$ 中出现 $2$ 个 $0$，所以 $res+=f[3][2]$，$f[3][2]$ 中的 $3$ 表示从后 $3$ 位中取，$f[3][2]$ 中的 $2=K-last=2-0$；当第一位为 $1$，那后 $3$ 位就不能随便取，不能超过 $1001$，所以 $a_{n-1}$ 只能取 $0$， $a_{n-2}$ 只能取 $0$，对于最后一位 $a_1$，如果 $a_1$ 放 $0$，$res+=f[0][1]$，如果走到 $a_1=1$ 说明 $n$ 这个数字本身满足转换为 $B$ 进制数后有 $K$ 个 $1$，其余位为 $0$，故 $res+=1$
  1. $x>1$ ：第 $i$ 位的放置分为三种情况
    1. 第 $i$ 位放 $0$，后面 $i-1$ 位上可以放 $k-last$ 个 $1$，$res+=f[i-1][k-last]$
    2. 第 $i$ 位放 $1$，后面 $i-1$ 位上可以放 $k-last-1$ 个 $1$，$res+=f[i-1][k-last-1]$
    3. 第 $i$ 位放大于 $1$ 的数，已经不合题目要求（出现 $k$ 个 $1$，其余位都是 $0$），此时已经不合题意，直接剪枝 $break$

image-20240506203156130

  • 比如当 $n=99$ 时，转换成 $B=4$ 进制数后为 $1201$，从最高位 $a_n$ 开始枚举，如果 $a_n=0$，那么后 $3$ 位都能取 $[0,B-1]$，要在后 $3$ 位中放 $2$ 个 $1$，故有 $res+=f[3][2]$，如果 $a_n=1$，则现在还需在后 $3$ 位中放 $k-last=2-1=1$ 个 $1$，若第 $a_{n-1}$ 位取 $0,1$，则后 $2$ 位可以取 $[0,2]$，故有 $[1000,1033]$ 和 $[1100,1133]$，$res+=f[2][1]+f[2][0]$，如果 $a_{n-1}$ 取 $2$，此时不满足题目性质，故 $break$

3.3. 完整代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=34; // INT_MAX大约2×10^10,转换成2进制最多2^31,为了保险稍开大一点
int a[N];
int f[N][N]; // f[i][j]:表示i个位置上放置j个1的组合数,如C42=6,则f[4][2]=6
int K,B; // b进制表示,k个1

// 预处理组合数
void init() {
	for(int i=0;i<N;i++) f[i][0]=1; // Cn0=1,cnn的0在下方的递推式中可以得到为1
	for(int i=1;i<N;i++) {
		for(int j=1;j<=i;j++) {
			f[i][j]=f[i-1][j-1]+f[i-1][j]; // 组合数计算公式
			// c(i)(j)=c(i-1)(j-1)+c(i-1)(j)
		}
	}
}

int dp(int n) {
	int tmp=n; // 记录n
	if(!n) return 0; // 特判,n==0,则不存在满足这样性质的数字
	int cnt=0;
	while(n) a[++cnt]=n%B,n/=B; // 将n拆成B进制数字存储至数组a
	
	// 打印数字n和其转换后的结果
	cout<<tmp<<":";
	for(int i=1;i<=cnt;i++) {
		cout<<a[i];
	}
	cout<<endl;
	
	int res=0,last=0; // last表示第i位前放置1的个数(记录已经放置的1的个数)
	// 从高位到低位枚举
	for(int i=cnt;i>=1;i--) {
		int x=a[i]; // 取出an
		// 1) 第i位==0时,直接跳过枚举下一位(即不进入这个if中)
		// 2) 第i位==1时,则这一位可以放0或1
		if(x) {
			// 第一种情况:x位固定可以放0
			res+=f[i-1][K-last]; // 第i位放0,则从后i-1位中放K-last个0
			printf("(1)i=%d f[%d %d]=%d res=%d\n",i,i-1,K-last,f[i-1][K-last],res);
			// 第i位>1时,则可以取[0,1,...,ai-1]
			if(x>1) {
				if(K-last-1>=0) {
					// 第二种情况:x>1,在本位可以放1
					printf("(2)i=%d f[%d %d]=%d res=%d\n",i,i-1,K-last,f[i-1][K-last-1],res);
					res+=f[i-1][K-last-1]; // 第i位放1,则从后i-1位中放K-last-1个0
				}
				break; // 第i位放大于1的数,不合要求直接break
			} else {
				// 第i位==1时,不能使用组合数计算,则继续枚举下一位
				last++; // 出现的1的个数+1
				if(last>K) break; // 1的个数多余k,break
			}
		}
		if(i==1 && last==K) {
			// 第三种情况=> 走到数字本身
			res++; // 特判,走到末尾了,+1
			printf("(3)i=%d res=%d\n",i,res);
		}
	}
	return res;
}

int x,y;

int main() {
//	cout<<INT_MAX<<endl;
	cin>>x>>y>>K>>B;
	init();
	cout<<dp(y)-dp(x-1)<<endl;
	return 0;
}

3.4. 样例解析

  • 当 $n=65$ 时转换成 $4$ 进制数为 $1001$，从 $a4=1$ 开始枚举，若 $a4$ 取 $0$，则 $res+=f[i-1][k-last]=f[3][2]=3$；$a_3=0,\ a_2=0$，没有比其更小的数；$a_1=1$，若 $a_1$ 取 $0$，则 $res+=f[i-1]k-last=3$，最后走到 $a_1=1$，$1001$ 本身满足性质，所以 $res+=1==4$

image-20240506210646018

  • 当 $n=97$ 时转换成 $4$ 进制数为 $1201$，从 $a_4=1$ 开始枚举，若 $a_4$ 取 $0$，则 $res+=f[i-1][k-last]=f[3][2]=3$；$a_3=2$，则 $a_3$ 可以取 $[0,1]$，当 $a_3=0$ 时，$res+=f[i-1][k-last]=f[2][1]=2$，当 $a_3=1$ 时，$res+=f[i-1][k-last-1]=f[2][0]$，因为 $a_3=2>1$ 此时不满足题目性质，所以 $break$

image-20240506211653186

  • 当 $n=85$ 时转换成 $4$ 进制数为 $1111$，从 $a_4=1$ 开始枚举，若 $a_4$ 取 $0$，则 $res+=f[i-1][k-last]=f[3][2]=3$，$a_4=1$ 不用计算组合数跳过到下一位，继续枚举 $a_3=1$，若 $a_3$ 取 $0$，则 $res+=f[i-1][k-last]=f[2][1]=2$，若 $a_3=1$ 不用计算组合数跳过到下一位，继续枚举 $a_2=1$，若 $a_2$ 取 $0$，则 $res+=f[i-1][k-last]=f[1][0]=1$，若 $a_2$ 取 $1$，此时 $last==3>k$，则 $break$

image-20240506212218740

打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信