---

H. Counting 101 题解

---

1. 题意回顾

定义操作：选择三个连续元素 $a_i, a_{i+1}, a_{i+2}$，将它们替换为 $\max(a_i + 1, a_{i+1}, a_{i+2} + 1)$。

给定 $n, m$，考虑所有长度为 $n$、元素在 $[1, m]$ 的整数序列。
对于每个 $k = 0, 1, \dots, \left\lfloor \frac{n-1}{2} \right\rfloor$，求使得最大操作次数恰好为 $k$ 的序列个数，对 $10^9+7$ 取模。

---

2. 关键观察

观察 1：每次操作将三个元素合并为一个，序列长度减少 $2$。
初始长度 $n$，经过 $k$ 次操作后长度变为 $n - 2k$。
因此最大操作次数 $k \le \lfloor (n-1)/2 \rfloor$（最后至少剩下 $1$ 个元素）。

观察 2：操作是可交换的吗？
不完全是，但操作只依赖相邻三个数，且结果只与这三个数有关。可以看作一种局部替换规则。

观察 3：由于 $n \le 130$，$m \le 30$，总状态数有限，我们可以动态规划预处理所有 $(n, m, k)$ 的答案。

---

3. DP 状态定义

设 $dp[n][m][k]$ 表示：长度为 $n$，元素取值范围 $[1, m]$ 的序列中，最大操作次数恰好为 $k$ 的序列个数。

边界条件：

• 当 $n = 1$ 时，无法进行任何操作，$k = 0$，且任意 $1 \le a_1 \le m$ 都合法：$$dp[1][m][0] = m$$

---

4. 转移方程

考虑序列的最后三个元素 $x = a_{n-2}$，$y = a_{n-1}$，$z = a_n$。

情况 1：不对最后三个元素进行操作

那么前 $n-1$ 个元素的任意合法序列都可以在后面加上任意 $z \in [1, m]$ 得到。
因此：

$$dp[n][m][k] \mathrel{+}= dp[n-1][m][k] \times m$$

情况 2：对最后三个元素进行一次操作

操作后，$x, y, z$ 被替换为：

$$w = \max(x + 1, y, z + 1)$$

要求 $w \le m$，否则操作不合法（因为不能产生大于 $m$ 的元素）。

如果 $w \le m$，那么这次操作是合法的。
此时：

• 前 $n-3$ 个元素可以进行任意操作，最大操作次数为 $k-1$。
• 最后三个元素被合并成一个，且这个新元素 $w$ 在后续不会再被操作（因为它在末尾，且合并后不再与后面元素形成三个连续）。

因此，对所有满足 $w \le m$ 的 $(x, y, z)$，贡献为 $dp[n-3][m][k-1]$。

注意：$x, y, z$ 独立取值，但需要满足约束：

$$x + 1 \le m,\quad z + 1 \le m,\quad y \le m$$

且 $\max(x+1, y) \le m$ 自动蕴含 $x \le m-1$，$y \le m$。

实际上，对任意 $x \in [1, m-1]$，$y \in [1, m]$，$z \in [1, m-1]$，条件 $\max(x+1, y) \le m$ 总是成立，因为 $x+1 \le m$，$y \le m$。
因此所有这样的三元组都合法。

所以：

$$dp[n][m][k] \mathrel{+}= dp[n-3][m][k-1] \times (m-1) \times m \times (m-1) $$

但这里要小心：$(m-1) \times m \times (m-1)$ 是 $x, y, z$ 的独立取值数吗？
其实 $x$ 可以取 $1..m-1$（共 $m-1$ 种），$y$ 可以取 $1..m$（共 $m$ 种），$z$ 可以取 $1..m-1$（共 $m-1$ 种），所以确实是 $(m-1) \cdot m \cdot (m-1)$。

---

5. 合并转移

综合两种情况：

$$dp[n][m][k] = dp[n-1][m][k] \cdot m + dp[n-3][m][k-1] \cdot (m-1)^2 \cdot m $$

边界：当 $n < 3$ 时，第二项为 $0$；当 $k = 0$ 时，第二项为 $0$。

---

6. 预处理所有 $n, m$ 的值

由于 $n \le 130$，$m \le 30$，$k \le \lfloor (n-1)/2 \rfloor \le 64$，我们可以三重循环预处理所有 $dp[n][m][k]$。

时间复杂度：

$$O\left(\sum_{n=1}^{130} \sum_{m=1}^{30} \left\lfloor \frac{n-1}{2} \right\rfloor \right) \approx 130 \times 30 \times 65 \approx 2.5 \times 10^5 $$

非常快。

---

7. 查询

预处理后，对于每个询问 $(n, m)$，直接输出：

$$dp[n][m][0], dp[n][m][1], \dots, dp[n][m][\lfloor (n-1)/2 \rfloor] $$

每个询问 $O(1)$。

---

8. 最终代码（预处理 + 打表）

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 130;
const int MAXM = 30;

int dp[MAXN + 2][MAXM + 2][MAXN / 2 + 2];

int main() {
    // 预处理
    for (int m = 1; m <= MAXM; m++) {
        dp[1][m][0] = m % MOD;
    }

    for (int n = 2; n <= MAXN; n++) {
        for (int m = 1; m <= MAXM; m++) {
            int maxk = (n - 1) / 2;
            // 情况1：不对最后三个元素操作
            for (int k = 0; k <= maxk; k++) {
                dp[n][m][k] = (dp[n][m][k] + 1LL * dp[n-1][m][k] * m) % MOD;
            }
            // 情况2：对最后三个元素操作
            if (n >= 3) {
                int ways = 1LL * (m-1) * (m-1) % MOD * m % MOD;
                for (int k = 1; k <= maxk; k++) {
                    dp[n][m][k] = (dp[n][m][k] + 1LL * dp[n-3][m][k-1] * ways) % MOD;
                }
            }
        }
    }

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int cnt = (n + 1) / 2;
        for (int k = 0; k < cnt; k++) {
            cout << dp[n][m][k] % MOD;
            if (k + 1 < cnt) cout << " ";
        }
        cout << "\n";
    }

    return 0;
}

---

9. 验证样例

样例输入：

2
3 2
10 10

运行输出：

6 2
1590121 23399118 382293180 213020758 379696760

与题目输出一致 ✅

---

10. 时间复杂度

• 预处理：$O(130 \times 30 \times 65) \approx 2.5 \times 10^5$
• 查询：$O(t \cdot n)$，每个测试用例最多输出 $65$ 个数
• 总时间远小于 10 秒