参考《算法竞赛进阶指南》、AcWing题库

计数类DP

我们通过几道例题来介绍动态规划中的计数问题和数位统计问题。这两类问题都特别强调 “不重不漏”, 统计对象的可能情况一般比较多, 通常需要精确的划分和整体性的计算。因此, 使用动态规划抽象出问题中的 “子结构” 和推导 的 “阶段”, 将有助于我们准确而高效地进行求解。

306. 杰拉尔德和巨型象棋

给定一个 H×WH \times W 的棋盘，棋盘上只有 NN 个格子是黑色的，其他格子都是白色的。

在棋盘左上角有一个卒，每一步可以向右或向下移动一格，并且不能移动到黑色格子中。

求这个卒从左上角移动到右下角，一共有多少种路线。

输入格式

第一行包含三个整数 H,W,NH,W,N。

接下来 NN 行，每行包含两个整数 x，yx，y，描述一个黑色格子位于 xx 行 yy 列。

数据保证左上角和右下角的格子都是白色的。

输出格式

输出一个整数表示结果对 109+710^9+7 取模后的值。

数据范围

1≤H,W≤1051 \le H,W \le 10^5,
1≤N≤20001 \le N \le 2000

输入样例1：

1
2
3
3 4 2 
2 2 
2 3

输出样例1：

1
2

输入样例2：

1
2
3
4
100 100 3
15 16
16 15
99 88

输出样例2：

1
545732279

算法分析

棋盘上的白色格子数量巨大, 而黑色格子最多只有 2000 个。我们应该考虑如何依靠黑色格子进行计数。如果这个卒能走进黑色格子, 那么从左上角走到右下角的路线总数就是 CH+W−2H−1C_{H+W-2}^{H-1}, 我们在 “组合计数” 中提到过这个公式。若我们再求出从左上角到右下角经过了至少一个黑色格子的路线数量, 二者相减就得到了只经过白色格子的路线数。

把所有黑色格子按照行、列坐标递增的顺序排序。特别地, 我们假设左上角是第 0 个黑色格子, 右下角是第 N+1N+1 个黑色格子。设第 ii 个黑色格子在第 xix_{i} 行第 yiy_{i} 列。设 F[i]F[i] 表示从左上角走到排序后的第 ii 个黑色格子, 并且途中不经过其他黑色格子的路线数。

F[i]=Cxi−1+yi−1xi−1−∑j=0i−1F[j]∗Cxi−xj+yi−yjxi−xj, 其中 xi≥xj,yi≥yjF[i]=C_{x_{i}-1+y_{i}-1}^{x_{i}-1}-\sum_{j=0}^{i-1} F[j] * C_{x_{i}-x_{j}+y_{i}-y_{j}}^{x_{i}-x_{j}}, \text { 其中 } x_{i} \geq x_{j}, y_{i} \geq y_{j}

上式的含义是, 枚举 jj 作为从左上角到 (xi,yi)\left(x_{i}, y_{i}\right) 经过的第一个黑色格子。也就是从左上角到 (xj,yj)\left(x_{j}, y_{j}\right) 不能经过其他黑格子, 路线数为 F[j]F[j] 。从 (xj,yj)\left(x_{j}, y_{j}\right) 到 (xi,yi)\left(x_{i}, y_{i}\right) 随便走, 路线数就是一个组合数。等式中求和符号的部分求出了从左上角到 (xi,yi)\left(x_{i}, y_{i}\right), 途中经过至少一个黑色格子的路线数, 用总数减掉, 就得到了 F[i]F[i] 。

我们为什么这样设计状态转移方程? 为什么限制 jj 作为经过的第一个黑色格子呢? 请读者回顾 “区间 DP” 中的 “金字塔”一题, 在该题中我们提到, 一个状态划分成的若干个子问题之间应该具有互斥性, 才不会造成重复统计。实际上, 我们在求解计数类动态规划问题时, 通常要找到一个 “基准点”, 围绕这个基准点构造一个不可划分的 “整体”, 以避免子问题之间的重叠。既然需要求出从左上角到 (xi,yi)\left(x_{i}, y_{i}\right) 途中经过至少一个黑色格子的路线数, 就枚举第一个经过的黑色格子 jj, 使左上角到 jj 构成一个整体, 让这段路程只能经过白色格子, 不能再进行拆分。因为第一个经过的黑色格子不同, 所以不同的 jj 对应的路线肯定不会重复。而 jj 又取遍了 ii 之前的所有黑色格子, 所以路线也不会遗漏。结合乘法原理和加法原理, 我们就得到了状态转移方程中求和符号的部分。

以 F[0]=1F[0]=1 为初值, 计算上面的状态转移方程, 最终 F[N+1]F[N+1] 就是本题的答案。 对于组合数, 可以预处理阶乘关于 109+710^{9}+7 的乘法逆元来计算。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
#define x first
#define y second
const int SIZE = 2010;
pair<int, int> a[SIZE];
int h, w, n, f[SIZE], mod = 1000000007;
long long jc[200010], jcinv[200010];

int C(int n, int m) {
	return jc[n] * jcinv[m] % mod * jcinv[n - m] % mod;
}

long long power(long long a, int b) {
	long long c = 1;
	for (; b; b >>= 1) {
		if (b & 1) c = c*a%mod;
		a = a*a%mod;
	}
	return c;
}

int main() {
	jc[0] = 1, jcinv[0] = 1;
	for (int i = 1; i <= 200000; i++) {
		jc[i] = jc[i - 1] * i % mod;
		jcinv[i] = power(jc[i], mod - 2);
	}
	cin >> h >> w >> n;
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].x, &a[i].y);
	sort(a + 1, a + n + 1);
	a[n + 1].x = h, a[n + 1].y = w;
	for (int i = 1; i <= n + 1; i++) {
		f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
		for (int j = 1; j < i; j++) {
			if (a[j].x > a[i].x || a[j].y > a[i].y) continue;
			f[i] = (f[i] - (long long)f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x)) % mod;
		}
	}
	cout << (f[n + 1] + mod) % mod << endl;
}

Solution

307. 连通图

求 NN 个节点的无向连通图有多少个，节点有标号，编号为 1∼N1 \sim N。

例如下列图示，三个节点的无向连通图共 44 个。

输入格式

输入包含多组测试数据。

每组数据包含一个整数 NN。

当输入为 00 时，表示输入终止。

输出格式

每组测试数据输出一个结果，每个结果占一行。

数据范围

1≤N≤501 \le N \le 50

输入样例：

1
2
3
4
5
1
2
3
4
0

输出样例：

1
2
3
4
1
1
4
38

算法分析

在计数类动态规划中, 通常要把一个问题划分成若干个子问题, 以便于执行递推。一个连通图不容易进行划分, 而一个不连通的无向图则很容易划分成节点更少的两部分。所以我们可以考虑求出 NN 个点的无向图总数, 减去 NN 个点的不连通无向图的数量, 就是 NN 个点的连通无向图个数。

NN 个点的无向图总数显然是 2N∗(N−1)/22^{N *(N-1) / 2} 。含义是 NN 个点的无向图至多有 N∗(N−1)/2N * (N-1) / 2 条边, 每条边可有可无, 所以共有 2N∗(N−1)/22^{N *(N-1) / 2} 张不同的无向图。

接下来计算 NN 个点的不连通无向图的数量。一张不连通的无向图必定由若干个连通块构成。根据上一题提到的 “围绕基准点构造一个整体” 的思想, 我们可以枚举标号为 1 的节点所在的连通块包含的节点个数 kk, 从 2∼N2 \sim N 这 N−1N-1 个节点中选出 k−1k-1 个, 与 1 号节点一起构成大小为 kk 的连通块。显然, 我们有 CN−1k−1C_{N-1}^{k-1} 种选法。剩余 N−kN-k 个节点构成任意无向图, 有 2(N−k)∗(N−k−1)/22^{(N-k) *(N-k-1) / 2} 种方法。

综上所述, 设 F[i]F[i] 表示 ii 个节点的无向连通图个数, 状态转移方程为:

F[i]=2i∗(i−1)/2−∑j=1i−1F[j]∗Ci−1j−1∗2(i−j)∗(i−j−1)/2F[i]=2^{i *(i-1) / 2}-\sum_{j=1}^{i-1} F[j] * C_{i-1}^{j-1} * 2^{(i-j) *(i-j-1) / 2}

初值: F[1]=1F[1]=1 。目标: F[N]F[N] 。 .

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
85
86
87
//Author:XuHt
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 60, S = 600;
int n;
struct A {
	int a[S], len;
	inline A operator / (const int x) const {
		A ans;
		memset(ans.a, 0, sizeof(ans.a));
		ans.len = 0;
		int num = 0;
		for (int i = len; i; i--) {
			num = num * 10 + a[i];
			ans.a[i] = num / x;
			num %= x;
			if (!ans.len && ans.a[i]) ans.len = i;
		}
		return ans;
	}
	inline A operator + (const A x) const {
		A ans;
		memset(ans.a, 0, sizeof(ans.a));
		for (int i = 1; i <= max(len, x.len); i++) {
			ans.a[i] += a[i] + x.a[i];
			ans.a[i+1] = ans.a[i] / 10;
			ans.a[i] %= 10;
		}
		ans.len = max(len, x.len);
		if (ans.a[ans.len+1]) ++ans.len;
		return ans;
	}
	inline A operator * (const A x) const {
		A ans;
		memset(ans.a, 0, sizeof(ans.a));
		for (int i = 1; i <= len; i++)
			for (int j = 1; j <= x.len; j++) {
				ans.a[i+j-1] += a[i] * x.a[j];
				ans.a[i+j] += ans.a[i+j-1] / 10;
				ans.a[i+j-1] %= 10;
			}
		ans.len = len + x.len - 1;
		if (ans.a[ans.len+1]) ++ans.len;
		return ans;
	}
} f[N], p[N];

inline A C(int x, int y) {
	A ans;
	ans.len = ans.a[1] = 1;
	for (int i = y, j = 1; j <= x; i--, j++) {
		int t = i;
		A tmp;
		tmp.len = 0;
		while (t) {
			tmp.a[++tmp.len] = t % 10;
			t /= 10;
		}
		ans = ans * tmp / j;
	}
	return ans;
}

inline void print(A x) {
	for (int i = x.len; i; i--) printf("%d", x.a[i]);
	puts("");
}

int main() {
	for (int i = 1; i <= 50; i++) {
		ll t = (1ll << i) - 1;
		while (t) {
			p[i].a[++p[i].len] = t % 10;
			t /= 10;
		}
	}
	f[1].len = f[2].len = f[1].a[1] = f[2].a[1] = 1;
	for (int i = 3; i <= 50; i++)
		for (int j = 1; j <= i - 1; j++)
			f[i] = f[i] + C(j - 1, i - 2) * f[j] * f[i-j] * p[j];
	while (cin >> n && n) print(f[n]);
	return 0;
}

Solution

308. 它们中的多少个

在无向连通图中，若一条边被删除后，图会分成不连通的两部分，则称该边为割边。

求满足如下条件的无向连通图的数量：

1、由 NN 个节点构成，节点有标号，编号为 1∼N1 \sim N。

2、割边不超过 MM 条。

3、没有自环和重边。

注意

本题遵循书中所述，割边限制为不超过 MM 条，输入输出也与题目描述保持一致。

与 Conster Hunter 网站关于本题的描述和要求略有不同。

输入格式

输入共一行，包含两个整数 NN 和 MM。

输出格式

输出一个整数表示满足条件的无相连通图的数量对 109+710^9+7 取模后的结果。

数据范围

2≤N≤502 \le N \le 50,
0≤M≤N∗(N−1)/20 \le M \le N*(N-1)/2

输入样例：

1
3 3

输出样例：

1
4

算法分析

Solution

309. 装饰围栏

有 NN 块长方形的木板，长度分别为 1,2,…,N1,2,…,N，宽度都是 11。

现在要用这 NN 块木板组成一个宽度为 NN 的围栏，满足在围栏中，每块木板两侧的木板要么都比它高，要么都比它低。

也就是说，围栏中的木板是高低交错的。

我们称“两侧比它低的木板”处于高位，“两侧比它高的木板”处于低位。

显然，有很多种构建围栏的方案。

每个方案可以写作一个长度为 NN 的序列，序列中的各元素是木板的长度。

把这些序列按照字典序排序，如下图所示，就是 N=4N=4 时，所有满足条件的围栏按照木板长度的字典序排序后的结果。

现在给定整数 CC，求排名为 CC 的围栏中，各木板的长度从左到右依次是多少。

输入格式

第一行包含整数 KK，表示一共有 KK 组数据。

接下来 KK 行，每行包含一组数据，包括两个整数 NN 和 CC。

输出格式

每组数据输出一行结果，结果表示排名为 CC 的围栏中，各木板的长度从左到右排成的序列。

同行数据用空格隔开。

数据范围

1≤N≤201 \le N \le 20,
0<C<2630 < C < 2^{63}

输入样例：

1
2
3
2
2 1
3 3

输出样例：

1
2
1 2
2 3 1

算法分析

类似于倍增优化 DP 中的 “拼凑” 思想, 我们可以用 “试填法” 来确定排名为 CC 的栅栏中各木板的长度。具体来说, 我们可以从小到大枚举第一块木板的长度, 当第一块木板长度为 hh 时, 设后面 N−1N-1 块木板构成栅栏的方案数为 TT, 若 T≥CT \geq C, 则说明第一块木板的长度就应该是 hh, 可以继续尝试确定第二块木板的长度。否则, 说明第一块木板应该更长, 此时令 CC 减去 T,hT, h 增加 1 , 重复上述判断。为了让 “试填法” 更加高效, 我们需要预处理 TT 的值。

设 F[i,j,k]F[i, j, k] 表示用 ii 块长度不同的木板构成栅栏, 其中最左边的木板的长度从小到大排在第 jj 位, 并且位置状况为 kk （k=0k=0 表示处于低位, k=1k=1 表示处于高位）的方案总数。状态转移方程为:

F[i,j,0]=∑p=ji−1F[i−1,p,1]F[i,j,1]=∑p=1j−1F[i−1,p,0]\begin{align} F[i, j, 0]=\sum_{p=j}^{i-1} F[i-1, p, 1]\\ F[i, j, 1]=\sum_{p=1}^{j-1} F[i-1, p, 0] \end{align}

注意, 在动态规划的状态表示中, 我们没有采取像 “用长度为 1∼i1 \sim i 的木板、最左边的长度为 jj ” 这种长度绝对确定的表述, 而是把 ii 和 jj 依据相对大小顺序进行定义。这是因为以下两个子问题其实是等价的:

  1. 用长度为 1∼i1 \sim i 的木板构成栅栏, 其中最左边的长度为 jj 。
  2. 用 ii 块长度不同的木板构成栅栏, 其中最左边的长度排名为 jj 。

实际上我们之前多次使用的 “离散化” 思想, 就与上面这种 “等效代换” 思想的本质是相同的。利用上面两个子问题的等价性, 我们在进行状态转移,数量统计时会非常容易。

在完成动态规划预处理后, 就可以执行 “试填法” 了。

假设已经确定了从左到右前 i−1i-1 块木板的长度, 现在正在考虑第 ii 块木板。记
录上一块木板的长度 lastlast 、上一块木板的高低位置情况 kk （ k=0k=0 表示低位, k=1k=1 表示高位。）

把 kk 赋值为 k  xor  1k \;xor\; 1 , 即可得到第 ii 块木板应该处于高位还是低位。

特别地, 第 1 块木板既可能处于高位, 也可能处于低位。所以要注意单独处理, 先确定下来第 1 块木板的高度和位置情况, 作为 lastlast 和 kk 的初始值。

从小到大枚举第 ii 块木板的长度, 设它的真实长度为 lenlen , 该长度在剩余木板中从小到大排名为 jj 。若 kk 为 0 , 需要满足 len<lastlen < last , 否则应满足 len>lastlen > last。

若 F[N−i+1,j,k]<CF[N-i+1, j, k]<C, 则令 CC 减掉 F[N−i+1,j,k]F[N-i+1, j, k], 继续尝试更大的 jj 。

否则, 第 ii 块木板的长度就应该是 lenlen , 可以把它输出。然后, 令 ii 增加 1 , 考虑下一块木板。

最后, 我们就得到了所求的栅栏方案。动态规划的时间复杂度为 O(N3)O\left(N^{3}\right), 试填过程的时间复杂度为 O(N2)O\left(N^{2}\right) 。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t, n;
long long m, f[21][21][2];

void prework() {
	f[1][1][0] = f[1][1][1] = 1;
	for (int i = 2; i <= 20; i++)
		for (int j = 1; j <= i; j++) {
			for (int p = j; p <= i - 1; p++)
				f[i][j][0] += f[i - 1][p][1];
			for (int p = 1; p <= j - 1; p++)
				f[i][j][1] += f[i - 1][p][0];
		}
}

int main()
{
	prework();
	cin >> t;
	while (t--) {
		cin >> n >> m;
		bool used[21];
		memset(used, 0, sizeof(used));
		int last, k;
		// 第1块木板，既可能处于高位，也可能处于低位，单独处理
		for (int j = 1; j <= n; j++) {
			if (f[n][j][1] >= m) {
				last = j, k = 1;
				break;
			}
			else m -= f[n][j][1];
			if (f[n][j][0] >= m) {
				last = j, k = 0;
				break;
			}
			else m -= f[n][j][0];
		}
		used[last] = 1;
		printf("%d", last);
		// 第2~n块木板，高低位置、合法的长度范围与上一块木板有关
		for (int i = 2; i <= n; i++) {
			k ^= 1;
			// 真实长度为len，在剩余木板中排名为j
			int j = 0;
			for (int len = 1; len <= n; len++) {
				if (used[len]) continue;
				j++;
				if (k == 0 && len < last || k == 1 && len > last) {
					if (f[n - i + 1][j][k] >= m) {
						last = len;
						break;
					}
					else m -= f[n - i + 1][j][k];
				}
			}
			used[last] = 1;
			printf(" %d", last);
		}
		puts("");
	}
}

Solution