序列子序列计数
题目描述
给定正整数 nnn 和 mmm，考虑所有长度为 nnn 的序列 a=(a1,a2,…,an)a = (a_1, a_2, \dots, a_n)a=(a1 ,a2 ,…,an )，其中每个元素均属于 [1,m][1, m][1,m]。
一个子序列可以通过删除原序列中的任意若干元素（也可以不删除），并保持剩余元素的相对顺序得到。两个子序列仅按得到的元素序列是否相同来区分，与选择的下标无关。空序列也被视为一个合法的子序列。
对于每个合法序列 aaa，统计它包含的不同子序列的数量。请你求出所有合法序列的这一数量之和，答案对 998244353998244353998244353 取模。
输入格式
第一行输入一个整数 TTT，表示测试数据组数。
接下来 TTT 行，每行输入两个整数 nnn 和 mmm，分别表示序列长度和元素的取值上界。
输出格式
对于每组测试数据，输出一行一个整数，表示所有合法序列包含的不同子序列数量之和对 998244353998244353998244353 取模后的结果。
数据范围
* 1≤T≤2×1051 \le T \le 2 \times 10^51≤T≤2×105
* 1≤n≤2×1051 \le n \le 2 \times 10^51≤n≤2×105
* 1≤m≤1061 \le m \le 10^61≤m≤106
* 所有测试数据满足 ∑n≤2×105\sum n \le 2 \times 10^5∑n≤2×105
样例输入
样例输出
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好。这是我的思路：
俺的思路
1. 核心思路：动态规划与贡献法 设 DP[I]DP[I]DP[I] 表示：所有长度为 III 的序列，其包含的不同子序列数量之和。 设 F(S)F(S)F(S) 表示序列 SSS 包含的不同子序列数量。 考虑如何从长度为 I−1I-1I−1 的序列转移到长度为 III 的序列： 对于任意一个长度为 I−1I-1I−1 的序列 SSS，我们在其末尾追加一个元素 X∈[1,M]X \IN [1, M]X∈[1,M]，得到新序列 S′S'S′。 根据经典的不同子序列计数方法，新序列 S′S'S′ 的不同子序列数量等于：
f(S′)=2×f(S)−Last(S,x)f(S') = 2 \times f(S) - \text{Last}(S, x) f(S′)=2×f(S)−Last(S,x)
其中： 关于 2timesf(S)2 times f(S)2timesf(S)：表示原有的所有子序列，加上每个原有子序列末尾拼上 xxx 得到的新子序列。 关于 Last(S,x)\text {Last}(S, x)Last(S,x)：表示在 SSS 中，上一次以 xxx 结尾的子序列数量（即追加 xxx 时产生的重复子序列数量）。
2. 全局求和与优化
我们现在要求的是所有长度为 iii 的序列的子序列数量之和，即 的序列的子序列数量之和，即 dp[i]dp[i]dp[i]。 我们对上述等式两边关于所有可能的 SSS 和 xxx 进行求和：
dp[i]=∑S∑x=1m(2×f(S)−Last(S,x))dp[i] = \sum_{S} \sum_{x=1}^m \left( 2 \times f(S) - \text{Last}(S, x) \right) dp[i]=S∑ x=1∑m (2×f(S)−Last(S,x))
拆分这个式子： 第一部分：
∑S∑x=1m2×f(S)=2m∑Sf(S)=2m⋅dp[i−1]\sum_{S} \sum_{x=1}^m 2 \times f(S) = 2m \sum_{S} f(S) = 2m \cdot dp[i-1] S∑ x=1∑m 2×f(S)=2mS∑ f(S)=2m⋅dp[i−1]
第二部分：
∑S∑x=1mLast(S,x)\sum_{S} \sum_{x=1}^m \text{Last}(S, x) S∑ x=1∑m Last(S,x)
我们需要计算第二部分。先固定一个序列 SSS，考察内层求和 ∑x=1mLast(S,x)\sum_ {x=1}^m \text {Last}(S, x)∑x=1m Last(S,x) 的含义： 定义解析：根据定义，Last(S,x)\text {Last}(S, x)Last(S,x) 是序列 SSS 中以元素 xxx 结尾的不同子序列的数量。 空集情况：如果序列 SSS 中根本不包含元素 xxx，那么 Last(S,x)=0\text {Last}(S, x) = 0Last(S,x)=0。 非空情况：如果序列 SSS 中包含元素 xxx，那么 Last(S,x)\text
{Last}(S, x)Last(S,x) 恰好等于 SSS 中所有以 xxx 结尾的不同子序列的数量。 因此，当我们对所有的 x∈[1,m]x \in [1, m]x∈[1,m] 求和时，实际上就是把序列 SSS 中所有以各种字符结尾的非空子序列重新按结尾字符归类并相加。这恰好等于序列 SSS 的非空子序列总数！ 即：
∑S∑x=1mLast(S,x)=∑S(f(S)−1)=∑Sf(S)−∑S1=dp[i−1]−mi−1\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} S∑ x=1∑m Last(S,x)=S∑ (f(S)−1)=S∑ f(S)−S∑ 1=dp[i−1]−mi−1
（因为长度为 i−1i-1i−1 的序列共有 mi−1m^{i-1}mi−1 个） 代入原式：
dp[i]=2m⋅dp[i−1]−(dp[i−1]−mi−1)dp[i] = 2m \cdot dp[i-1] - (dp[i-1] - m^{i-1}) dp[i]=2m⋅dp[i−1]−(dp[i−1]−mi−1)
dp[i]=(2m−1)⋅dp[i−1]+mi−1dp[i] = (2m - 1) \cdot dp[i-1] + m^{i-1} dp[i]=(2m−1)⋅dp[i−1]+mi−1
3. 边界条件与最终公式 边界条件：当 I=0I=0I=0 时，只有一个空序列，它包含 1 个不同子序列（即空子序列本身）。所以 DP[0]=1DP[0] = 1DP[0]=1。 递推公式：
dp[i]=(2m−1)⋅dp[i−1]+mi−1(mod998244353)dp[i] = (2m - 1) \cdot dp[i-1] + m^{i-1} \pmod{998244353} dp[i]=(2m−1)⋅dp[i−1]+mi−1(mod998244353)
4. CODE
复杂度
* 时间复杂度：对于每组测试数据，循环 nn 次，每次进行常数次乘加运算，时间复杂度为 O(n)O(n)O(n)O(n)O(n)O(n)。由于 ∑n≤2×105∑n≤2×105∑n≤2×105∑n≤2×105∑n≤2×105∑n≤2×105 ，总时间复杂度为 O(∑n)O(∑n)O(∑n)O(∑n)O(∑n)O(∑n) ，非常高效。
* 空间复杂度：O(1)O(1)O(1)，仅使用了几个变量。
宣传一下我和老师同学一起做的网站：https://shortestpath.cn
