题解 - CF2002H Counting 101

Luogu

题意

给定 $n$ 和 $m$。有一个 $k$，取值范围在 $[0,\left\lfloor\frac{n-1}{2}\right\rfloor]$。现在有个序列，其中每个元素的取值范围为 $[1, m]$。需要对这个序列进行任意多次操作，在每次操作中，选择三个连续的元素 $a_i, a_{i+1}, a_{i+2}$ 并将它们合并为一个元素 $ \max(a_i+1, a_{i+1}, a_{i+2}+1) $，最多可以进行的操作数就是 $k$。要找出整数序列 $a_1,a_2,\ldots,a_n$ 的数量，输出取模 $10^9+7$ 的结果。

包含多个测试样例，每个测试样例输入 $n$ 和 $m$，输出 $\left\lfloor\frac{n+1}{2}\right\rfloor$ 个数字，第 $i$ 个数字是有效序列的数量。

思路

考虑动态规划。对于长度为 $n$ 的序列，初始化操作次数为 $0$ 的情况，即没有任何操作时，只有一种序列是有效的，即所有元素都是 $1$。

接下来动态规划，计算不同长度 $n$、不同操作次数 $k$ 和不同最大值 $m$ 下的序列数量。

令 $dp(m,n,k)$ 表示在最大值限制为 $m$，序列长度为 $n$，操作次数为 $k$ 时的序列数量。

对于每个 $dp(m,n,k)$，考虑所有可能的子序列 $a_1, a_2, \ldots, a_{n-1}$，以及对应的操作次数 $k-1$（因为每次操作会减少两个元素），通过合并子序列的最后三个元素来更新当前状态。

处理序列长度为奇数和偶数时的特殊情况，确保在合并操作中不会越界。使用前缀和和差分数组来优化状态转移的计算，减少重复计算。

代码

代码中的数组意义解释：

jl[m][i]：用于存储 $j$ 从 $1$ 到 $i$ 的乘积，对 $m$ 取模的结果，用于快速计算组合数。
dp[m][n][k]：存储最终结果，即在最大值 $m$，序列长度 $n$，操作次数 $k$ 下的序列数量。
dpl[n][c][l] 和 dpr[n][c][r]：用于存储左半部分和右半部分的临时状态，以优化状态转移。
dp[m][n][k]：表示在最大值限制为 $m$，序列长度为 $n$，操作次数为 $k$ 时的序列数量。

代码： 

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

const int N = 130, M = 30;
const int mod =	1e9 + 7;

int T;
int dp[M + 5][N + 5][N / 2 + 5], dpl[N + 5][N + 5][N + 5], dpr[N + 5][N + 5][N + 5];
long long jl[M + 5][N + 5];

int main() {
	// 预处理阶乘模数
	for (int m = 1; m <= M; ++m) {
		jl[m][0] = 1;
		for (int i = 1; i <= N; ++i) {
			jl[m][i] = (long long) jl[m][i - 1] * m % mod;
		}
	}

	dp[1][0][0] = 1;
	for (int n = 1; n <= N; ++n) {
		dp[1][n][0] = 1;
	}

	int n_;
	for (int m = 2; m <= M; ++m) {
		// 初始化dpl和dpr数组
		for (int n = 0; n <= N; ++n) {
			for (int c = 0; c <= n; ++c) {
				for (int l = (n - c) % 2; c + l <= n; l += 2) {
					dpl[n][c][l] = 0;
				}
				for (int r = (n - c) % 2; c + r <= n; r += 2) {
					dpr[n][c][r] = 0;
				}
			}
		}

		// 更新dpl和dpr数组
		for (int n = 0; n <= N; ++n) {
			for (int k = 0; k <= n / 2; ++k) {
				if (!dp[m - 1][n][k]) {
					continue;
				}
				dpl[n][0][n - k * 2] = (dpl[n][0][n - k * 2] + dp[m - 1][n][k]) % mod;
				dpr[n][0][n] = (dpr[n][0][n] + dp[m - 1][n][k]) % mod;
			}
		}

		// 计算新的答案
		for (int n = 0; n <= N; ++n) {
			for (int c = 0; c <= n; ++c) {
				for (int l = (n - c) % 2; c + l <= n; l += 2) {
					if (!dpl[n][c][l]) {
						continue;
					}
					int k = (n - (c + (l == 0 ? 0 : (l - 1) % 2 + 1))) / 2;
					dp[m][n][k] = (dp[m][n][k] + dpl[n][c][l]) % mod;
				}
				for (int n1 = 0; (n_ = n + 1 + n1) <= N; ++n1) {
					for (int l = (n - c) % 2; c + l <= n; l += 2) {
						if (!dpl[n][c][l]) {
							continue;
						}
						if (l <= n1) {
							dpr[n_][c + 1][n1 - l] = (dpr[n_][c + 1][n1 - l] + (long long) dpl[n][c][l] * jl[m - 1][n1]) % mod;
						} else {
							int c_, r_;
							if (!n1 && !(l % 2)) {
								c_ = c + 3, r_ = 0;
							} else {
								c_ = c + 2, r_ = n1 - (l % 2 == 0 ? 1 : 0);
							}
							dpl[n_][c_][r_ % 2] = (dpl[n_][c_][r_ % 2] + (long long) dpl[n][c][l] * jl[m - 1][n1]) % mod;
							dpr[n_][c_][r_] = (dpr[n_][c_][r_] + (long long) dpl[n][c][l] * jl[m - 1][n1]) % mod;
						}
					}
					int r;
					for (r = (n - c) % 2; c + r <= n && r <= n1; r += 2) {
						if (!dpr[n][c][r]) {
							continue;
						}
						for (int k1 = 0; k1 * 2 <= n1; ++k1) {
							int tp_max = max((n1 - r) - k1 * 2, (n1 - r) % 2);
							dpl[n_][c + 1][tp_max] = (dpl[n_][c + 1][tp_max] + (long long) dpr[n][c][r] * dp[m - 1][n1][k1]) % mod;
						}
					}
					int x = 0;
					for ( ; c + r <= n; r += 2) {
						x = ((long long) x + dpr[n][c][r] - dpl[n][c][r] + mod) % mod;
					}
					int tp = (n1 + n - c) % 2;
					dpl[n_][c + 1][tp] = (dpl[n_][c + 1][tp % 2] + (long long) x * jl[m - 1][n1]) % mod;
				}
			}
		}
	}

	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		int n, m, k;
		scanf("%d%d", &n, &m);
		for (k = 0; k * 2 < n; ++k) {
			printf("%d ", dp[m][n][k]);
		}
		printf("\n");
	}
	return 0;
}