题解（团队内部题；组合数学好题）

Lag_longlong

2026-09-02 21:20:13

发布于：广东

6阅读

0回复

0点赞

序列子序列计数

题目描述

给定正整数 $n$ 和 $m$ ，考虑所有长度为 $n$ 的序列 $a = (a_1, a_2, \dots, a_n)$ ，其中每个元素均属于 $[1, m]$ 。

一个子序列可以通过删除原序列中的任意若干元素（也可以不删除），并保持剩余元素的相对顺序得到。两个子序列仅按得到的元素序列是否相同来区分，与选择的下标无关。空序列也被视为一个合法的子序列。

对于每个合法序列 $a$ ，统计它包含的不同子序列的数量。请你求出所有合法序列的这一数量之和，答案对 $998244353$ 取模。

输入格式

第一行输入一个整数 $T$ ，表示测试数据组数。

接下来 $T$ 行，每行输入两个整数 $n$ 和 $m$ ，分别表示序列长度和元素的取值上界。

输出格式

对于每组测试数据，输出一行一个整数，表示所有合法序列包含的不同子序列数量之和对 $998244353$ 取模后的结果。

数据范围

$1 \le T \le 2 \times 10^5$
$1 \le n \le 2 \times 10^5$
$1 \le m \le 10^6$
所有测试数据满足 $\sum n \le 2 \times 10^5$

样例输入

2
2 3
3 2

样例输出

33
46

好。这是我的思路：

俺的思路

1. 核心思路：动态规划与贡献法设 $dp[i]$ 表示：所有长度为 $i$ 的序列，其包含的不同子序列数量之和。设 $f(S)$ 表示序列 $S$ 包含的不同子序列数量。考虑如何从长度为 $i-1$ 的序列转移到长度为 $i$ 的序列：对于任意一个长度为 $i-1$ 的序列 $S$ ，我们在其末尾追加一个元素 $x \in [1, m]$ ，得到新序列 $S'$ 。根据经典的不同子序列计数方法，新序列 $S'$ 的不同子序列数量等于：

$f(S') = 2 \times f(S) - \text{Last}(S, x)$

其中：关于 $2 times f(S)$ ：表示原有的所有子序列，加上每个原有子序列末尾拼上 $x$ 得到的新子序列。 关于 $\text {Last}(S, x)$ ：表示在 $S$ 中，上一次以 $x$ 结尾的子序列数量（即追加 $x$ 时产生的重复子序列数量）。

2. 全局求和与优化

我们现在要求的是所有长度为 $i$ 的序列的子序列数量之和，即的序列的子序列数量之和，即 $dp[i]$ 。我们对上述等式两边关于所有可能的 $S$ 和 $x$ 进行求和：

$dp[i] = \sum_{S} \sum_{x=1}^m \left( 2 \times f(S) - \text{Last}(S, x) \right)$

拆分这个式子： 第一部分：

$\sum_{S} \sum_{x=1}^m 2 \times f(S) = 2m \sum_{S} f(S) = 2m \cdot dp[i-1]$

第二部分：

$\sum_{S} \sum_{x=1}^m \text{Last}(S, x)$

我们需要计算第二部分。先固定一个序列 $S$ ，考察内层求和 $\sum_ {x=1}^m \text {Last}(S, x)$ 的含义： 定义解析：根据定义， $\text {Last}(S, x)$ 是序列 $S$ 中以元素 $x$ 结尾的不同子序列的数量。 空集情况：如果序列 $S$ 中根本不包含元素 $x$ ，那么 $\text {Last}(S, x) = 0$ 。 非空情况：如果序列 $S$ 中包含元素 $x$ ，那么 $\text {Last}(S, x)$ 恰好等于 $S$ 中所有以 $x$ 结尾的不同子序列的数量。因此，当我们对所有的 $x \in [1, m]$ 求和时，实际上就是把序列 $S$ 中所有以各种字符结尾的非空子序列重新按结尾字符归类并相加。这恰好等于序列 $S$ 的非空子序列总数！即：

$\sum_{S} \sum_{x=1}^m \text{Last}(S, x) = \sum_{S} (f(S) - 1) = \sum_{S} f(S) - \sum_{S} 1 = dp[i-1] - m^{i-1}$

（因为长度为 $i-1$ 的序列共有 $m^{i-1}$ 个）代入原式：

$dp[i] = 2m \cdot dp[i-1] - (dp[i-1] - m^{i-1})$

$dp[i] = (2m - 1) \cdot dp[i-1] + m^{i-1}$

3. 边界条件与最终公式边界条件：当 $i=0$ 时，只有一个空序列，它包含 1 个不同子序列（即空子序列本身）。所以 $dp[0] = 1$ 。递推公式：

$dp[i] = (2m - 1) \cdot dp[i-1] + m^{i-1} \pmod{998244353}$

4. code

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

ll mod = 998244353;
ll nc(ll x, ll y) {
	ll dp = 1;
	x %= mod;
	while (y > 0) {
		if (y & 1) dp = dp * x % mod;
		x = x * x % mod;
		y =y / 2;
	}
	return dp;
}

void solve() {
	ll n, m;
	cin >> n >> m;

	ll cof = (2 * m % mod - 1 + mod) % mod; 
	ll dp = 1; 
	ll pow = 1;
	for (ll i = 1; i <= n; i++) {
		dp = (cof * dp % mod + pow) % mod;
		pow = pow * m % mod; 
	}
	cout << dp << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}