本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15818532.html

数位dp的引入

首先假设有一天，我们遇见一道题：

求在 [a,b][a,b] 的区间里，满足条件的数有多少个。

如果我们没学过数位dp，我们会打出这样一个暴力：

1
2
for(i=a; i<=b; ++i)
	if(check(i))  ++ans;

这样的时间复杂度是 O(n×check的时间复杂度)O(n\times \text{check的时间复杂度})

当 a,ba,b 很大时，我们就出现问题了。

这时，我们就需要数位dp。

数位dp，就是字面意思，按位dp。

从最高位开始，逐位确定。

数位dp一般是使用搜索+记忆化实现。

数位dp

首先我们来看一道题:

给出一个区间 [a,b][a,b]，求范围内不降数的个数。
不降数：从左到右各位数字成小于等于的关系，如 123，446
1≤a≤b≤231−11≤a≤b≤2^{31} −1

第一，也就是数位dp的最重要的地方：

用 bb 以内的减去 a−1a-1 以内的就是答案

那如何求某个数以内的呢？

我们可以dfs从高位到低位确定！

首先，我们可以记录一下这是第几位。

那当前的枚举上限呢？

我们可以加一个参数，表示当前是否可以无限选。

那如何保持不降呢？

我们可以加一个参数，表示上一位是什么。

可是这时我们发现一个问题，上一位如果不存在怎么办？

我们可以再加一个参数，表示上一位是否存在！

然后统计答案即可。

于是，我们就打出一段代码了：

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
#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k; 
int x, y, a[15]; 

int dfs(int n, int lst, int p, int q) //数位dp 
{
	if(n==0) return 1; //搜完了 
	int i, k=0; 
	for(i=0; i<=9; ++i)
	{
		if(!p && i>a[n]) break;   //不超过原数 
		if(q && i<lst)  continue; //满足不降 
		k+=dfs(n-1, i, p|(i<a[n]), q||i); //加起来 
	} 
	return k; 
} //当前是第几位，上一位是什么，当前是不是可以随便填，首位是否确定 

int calc(int x) //拆数 
{
	n=0; 
	while(x) a[++n]=x%10, x/=10; 
	return dfs(n, 0, 0, 0); 
}

signed main()
{
	while(scanf("%d%d", &x, &y)!=EOF) 
		printf("%d\n", calc(y)-calc(x-1)); //相减 
	return 0; 
}

可是，这样子不会超时吗？

不会，因为数据弱

但我们可以让它更优！

crxis：先爆搜，爆搜不行减枝，减枝不行记忆化，记忆化不行倒搜、广搜或dp

于是我们可以加上记忆化：

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
#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k; 
int x, y, a[15];
int f[15][15][2][2];  

int dfs(int n, int lst, int p, int q) //数位dp 
{
	if(n==0) return 1; //搜完了 
	int i, k=0; 
	if(f[n][lst][p][q]!=-1) return f[n][lst][p][q]; //记忆化 
	for(i=0; i<=9; ++i)
	{
		if(!p && i>a[n]) break;   //不超过原数 
		if(q && i<lst)  continue; //满足不降 
		k+=dfs(n-1, i, p|(i<a[n]), q||i); //加起来 
	} 
	return f[n][lst][p][q]=k; 
} //当前是第几位，上一位是什么，当前是不是可以随便填，首位是否确定 

int calc(int x) //拆数 
{
	n=0; 
	memset(f, -1, sizeof(f)); //多测清空 
	while(x) a[++n]=x%10, x/=10; 
	return dfs(n, 0, 0, 0); 
}

signed main()
{
	while(scanf("%d%d", &x, &y)!=EOF) 
		printf("%d\n", calc(y)-calc(x-1)); //相减 
	return 0; 
}

思考：如何让参数减少？

例题

例题1

求 [a,b][a, b] 里有多少数相邻数字之间的差大于等于是2？
100% 的数据，满足 1≤A≤B≤2×1091≤A≤B≤2×10^9

数位dp，用 bb 以内的减去 a−1a-1 以内的就是答案。

dfs过程中记四维状态：当前到第几位？上一位是什么？前面的数是否小于原数？最高位确定了吗？

然后判断一下太大和相邻小于2的情况即可。

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
#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k; 
int x, y, a[15]; 
int f[15][15][2][2]; 

int dfs(int n, int lst, int p, int q)//数位dp 
{
	if(n==0) return 1; //搜完了 
	int i, k=0; 
	if(f[n][lst][p][q]!=-1) return f[n][lst][p][q]; //记忆化 
	for(i=0; i<=9; ++i)
	{
		if(!p && i>a[n]) break; //不超过原数 
		if(q && abs(i-lst)<2)  continue; //相邻之差大于等于2 
		k+=dfs(n-1, i, p|(i<a[n]), q||i); //加起来 
	} 
	return f[n][lst][p][q]=k; 
}//当前是第几位，上一位是什么，当前是不是可以随便填，首位是否确定 

int calc(int x) //拆数 
{
	n=0;  
	memset(f, -1, sizeof(f)); //多测清空 
	while(x) a[++n]=x%10, x/=10; 
	return dfs(n, 0, 0, 0); 
}

signed main()
{ 
	while(scanf("%d%d", &x, &y)!=EOF) 
		printf("%d\n", calc(y)-calc(x-1)); //相减
	return 0; 
}

例题2

求 [n,m][n,m] 里不含4和62数的个数。
0<n≤m<1070<n≤m<10^7

数位dp。

判断两种情况：

  1. 当前数不为4
  2. 如果上一位为6，则这一位不为2

然后就搞定了。

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
#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k; 
int x, y, a[15]; 
int f[15][15][2]; 

int dfs(int n, int lst, int p) //数位dp 
{
	if(n==0) return 1; //搜完了 
	int i, k=0; 
	if(f[n][lst][p]!=-1) return f[n][lst][p]; //记忆化
	for(i=0; i<=9; ++i)
	{
		if(!p && i>a[n]) break; //不超过原数 
		if(i==4) continue; //不含4 
		if(lst==6&&i==2) continue; //上一位为6，这一位不为2 
		k+=dfs(n-1, i, p|(i<a[n])); 
	}
	return f[n][lst][p]=k; 
} //当前是第几位，上一位是什么，当前是不是可以随便填

int calc(int x) //拆数 
{
	n=0; 
	memset(f, -1, sizeof(f)); //多测清空 
	while(x) a[++n]=x%10, x/=10; 
	return dfs(n, 0, 0); 
}

signed main()
{
	scanf("%d%d", &x, &y); 
	while(x&&y) 
		printf("%d\n", calc(y)-calc(x-1)), //相减 
		scanf("%d%d", &x, &y); 
	return 0; 
}

例题3

求 [a,b][a, b] 里有多少数数字之和模 NN 为0？
对于全部数据，1≤a,b≤231−1,1≤N<1001≤a,b≤2^{31} −1,1≤N<100

数位dp。

三个转态：当前第几位？现在这一位是否有上限？当前和模 NN 是多少？

搜索是判断一下上下界，搜完后判断一下模 NN 余数即可。

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
#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k; 
int f[15][2][110]; 
int a[15], x, y; 

int dfs(int n, int p, int s)
{
	if(n==0) return (s%m==0 ? 1 : 0); 
	int i, k=0; 
	if(f[n][p][s]!=-1) return f[n][p][s]; 
	for(i=0; i<=9; ++i)
	{
		if(!p && i>a[n]) break;  
		k+=dfs(n-1, p|(i<a[n]), (s+i)%m); 
	}
	return f[n][p][s]=k; 
}

int calc(int x)
{
	memset(f, -1, sizeof(f)); n=0; 
	while(x) a[++n]=x%10, x/=10; 
	return dfs(n, 0, 0); 
}

signed main()
{ 
	while(scanf("%d%d%d", &x, &y, &m)!=EOF) 
		printf("%d\n", calc(y)-calc(x-1)); 
	return 0; 
}

例题4

在 [x,y][x,y] 中，BB 进制下有 kk 位为1，其它位都为0的方案数。
对于全部数据，1≤X≤Y≤231−1,1≤K≤20,2≤B≤101≤X≤Y≤2^{31}−1,1≤K≤20,2≤B≤10

这题稍微有点变形。

但其实我们只需要把 x,yx,y 转化为 BB 进制后照做即可。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, i, j, k; 
int b, a[50], f[50][2][30]; 
int x, y; 

int dfs(int n, int p, int k)
{
	if(n==0) return k==0 ? 1 : 0; 
	if(f[n][p][k]!=-1) return f[n][p][k]; 
	int i, s=0; 
	for(i=0; i<=1; ++i)	
	{
		if(!p && i>a[n]) break; 
		s+=dfs(n-1, p||(i<a[n]), k-i); 
	}
	return f[n][p][k]=s; 
}

int calc(int x)
{
	memset(f, -1, sizeof(f)); n=0; 
	while(x) a[++n]=x%b, x/=b; //进制转换 
	return dfs(n, 0, k); 
}

signed main()
{
	scanf("%lld%lld%lld%lld", &x, &y, &k, &b);  
	printf("%lld", calc(y)-calc(x-1)); 
	return 0; 
}

习题

习题1

求在 [a,ba,b] 中每个数码各出现了多少次。
100% 的数据中，1≤a≤b≤10121≤a≤b≤10^{12}

首先在数位dp中，对于当前枚举的数，乘上后面的方案数。

那么后面的数如何多次计算呢？

我们发现这些数具有传递性，于是我们每次可以把后面的数传到前面来。

然后在每次记忆化搜索返回时，顺便加上后面的数即可。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, i, j, k; 
int f[30][2][2], s[30][15][2][15], a[30], ans[15]; 
int x, y; 

int dfs(int k, int p, int o)
{
	if(k==0) return 1;  
	if(f[k][p][o]!=-1) 
	{
		for(int i=0; i<=9; ++i) ans[i]+=s[k][p][o][i]; 
		return f[k][p][o]; 
	}
	int i, j, q, z;  
	for(i=j=0; i<=9; ++i)
	{
		if(!p && i>a[k]) break; 
		q=dfs(k-1, p||(i<a[k]), o||i); 
		j+=q; 
		if(i||o) ans[i]+=q*m, s[k][p][o][i]+=q*m; 
		for(z=0; z<=9; ++z) s[k][p][o][i]+=s[k-1][p||(i<a[k])][o||i][z]; 
	}
	return f[k][p][o]=j; 
}

void clac(int x)
{
	memset(f, -1, sizeof(f)); 
	memset(s, n=0, sizeof(s)); 
	while(x) a[++n]=x%10, x/=10; 
	dfs(n, 0, 0); 
}

signed main()
{
	scanf("%lld%lld", &x, &y); 
	m=1; clac(y); m=-1; clac(x-1); 
	for(i=0; i<=9; ++i) printf("%lld ", ans[i]); 
	return 0; 
}

这道题总得来说还是不错的。

然而难点在于，当每次记忆化搜索返回时，后面的缺少统计了，于是我就尝试把他记起来。

然后又发现，在更后面的数又缺少统计，于是我发现这些统计的数由于记忆化搜索每次一样，所以具有传递性和普遍性，然后可以传递过来统计。

这也是数位dp的精妙之一。

习题2

求区间 [L,R][L,R] 内和 7 无关的数字的平方和
与7无关指不含7，不是7的倍数，数字之和不是7的倍数
1≤T≤50,1≤L≤R≤10181≤T≤50,1≤L≤R≤10^{18}

抛开平方和来说，这就是一道普通的数位dp。

但这题有平方和啊！

首先，假设当前这个数为 ab‾\overline{ab}，aa 为我们数位dp枚举的首位，bb 为后面的数，假设有 kk 位，然后让我们求在 aa 确定的情况下，所有 bb 的可能值下 ab‾\overline{ab} 的平方和，记为 Sab‾S_{\overline{ab}}

我们先用数位dp求一个 FbF_b，表示 bb 的方案数，于是上面的问题可以转化为：

Sab‾=∑Fb(ab‾)2\Large S_{\overline{ab}}=\sum^{F_b}(\overline{ab})^2

然后可以愉快地开始化简。

首先先把 ab‾\overline{ab} 变成一个数学式子：

Sab‾=∑Fb(a×10k+b)2\Large S_{\overline{ab}}=\sum^{F_b}(a\times 10^k+b)^2

后面有平方和公式拆开：

Sab‾=∑Fb(a2×102×k+2×a×10k×b+b2)\Large S_{\overline{ab}}=\sum^{F_b}(a^2\times 10^{2\times k}+2\times a\times 10^k\times b+b^2)

把 ∑Fb\sum^{F_b} 套进去：

Sab‾=Fb×a2×102×k+2×a×10k×∑Fbb+∑Fbb2\Large S_{\overline{ab}}=F_b\times a^2\times 10^{2\times k}+2\times a\times 10^k\times \sum^{F_b}b+\sum^{F_b}b^2

弄好看点：

Sab‾=Fba2102k+2×10ka∑Fbb+∑Fbb2\Large S_{\overline{ab}}=F_ba^210^{2k}+2\times10^ka\sum^{F_b}b+\sum^{F_b}b^2

显然 ∑Fbb2=Sb\sum^{F_b}b^2=S_b，因为这就是 SS 的定义：

Sab‾=Fba2102k+2×10ka∑Fbb+Sb\Large S_{\overline{ab}}=F_ba^210^{2k}+2\times10^ka\sum^{F_b}b+S_b

这个式子一看，还有 ∑Fbb\sum^{F_b}b 未知，怎么办？那我们就设 Tb=∑FbbT_b=\sum^{F_b}b。

于是式子就变成了这样：

Sab‾=Fba2102k+2×10kaTb+Sb\Large S_{\overline{ab}}=F_ba^210^{2k}+2\times10^kaT_b+S_b

然后我们来推一推 Tab‾T_{\overline{ab}} 吧。

Tab‾=∑Fbab‾\Large T_{\overline{ab}}=\sum^{F_b}\overline{ab}

拆一下 ab‾\overline{ab}：

Tab‾=∑Fb(a×10k+b)\Large T_{\overline{ab}}=\sum^{F_b}(a\times 10^k+b)

把 ∑Fb\sum^{F_b} 乘进去：

Tab‾=Fba10k+∑Fbb\Large T_{\overline{ab}}=F_ba10^k+\sum^{F_b}b

然后我们发现，∑Fbb\sum^{F_b}b 不就是 TbT_b 吗？然后套进去：

Tab‾=Fba10k+Tb\Large T_{\overline{ab}}=F_ba10^k+T_b

然后这道题就做成来了。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mo 1000000007
int n, m, i, j, k; 
int x, y, a[30], ten[10010]; 
int f[30][10][10][2]; 
int s[30][10][10][2]; 
int t[30][10][10][2]; 

int dfs(int n, int sum, int x, int p)
{
	if(n==0) return f[n][sum][x][p]=((sum%7>0 && x%7>0) ? 1 : 0); 
	int i, k=0, F, S, T; 
	if(f[n][sum][x][p]!=-1) return f[n][sum][x][p]; 
	for(i=0; i<=9; ++i)
	{
		if(!p && i>a[n]) break; 
		if(i==7) continue; 
		k+=dfs(n-1, (sum+i)%7, (x*10+i)%7, p|(i<a[n])); k%=mo;  
		F=f[n-1][(sum+i)%7][(x*10+i)%7][p|(i<a[n])]; 
		S=s[n-1][(sum+i)%7][(x*10+i)%7][p|(i<a[n])]; 
		T=t[n-1][(sum+i)%7][(x*10+i)%7][p|(i<a[n])]; 
		t[n][sum][x][p]+=(ten[n-1]*i%mo*F%mo+T)%mo; 
		s[n][sum][x][p]+=(ten[n-1]*ten[n-1]%mo*i%mo*i%mo*F%mo+ten[n-1]*i%mo*T%mo*2%mo+S)%mo; 
		t[n][sum][x][p]%=mo; s[n][sum][x][p]%=mo; 
	}
	return f[n][sum][x][p]=k; 
}

int calc(int x)
{
	memset(f, -1, sizeof(f)); 
	memset(s, n=0, sizeof(s)); 
	memset(t, 0, sizeof(t)); 
	while(x) a[++n]=x%10, x/=10; 
	dfs(n, 0, 0, 0); 
	return s[n][0][0][0]; 
}

signed main()
{ 
	for(i=ten[0]=1; i<=10000; ++i) ten[i]=ten[i-1]*10%mo; 
	scanf("%lld", &m); 
	while(m--) 
		scanf("%lld%lld", &x, &y), 
		printf("%lld\n", ((calc(y)-calc(x-1))%mo+mo)%mo); 
	return 0; 
}

这道题真得是一道不错的题。

很好的数位dp+推式子。

这道题推式子的过程有点烦，但我也明白，做数位dp的过程本质上就是个递归，每一步考虑一下自己本身，答案就是对的。