The 2025 Jiangsu Collegiate Programming Contest(2025 江苏省赛)——H. Loose Subsequences(求本质不同子序列的方法) · znzryb
## 题目大意
**题目描述**
给定一个长度为 $n$、仅由小写字母组成的字符串 $S$ 以及一个非负整数 $k$。
需要计算 $S$ 的本质不同的非空 $k$**-松散子序列**的数量,并将结果对 $998244353$ 取模。
**相关定义**
- $k$**-松散子序列**:如果子序列 $T$ 在原字符串 $S$ 中对应的下标序列为 $pos_1, pos_2, \dots, pos_m$,且满足对于所有的 $i \in [1, m-1]$,都有 $pos_{i+1} - pos_i > k$,那么 $T$ 就是一个 $k$-松散子序列。即子序列中原串相邻提取字符的原始位置距离必须严格大于 $k$。
- **本质不同**:两个子序列被认为是不同的,当且仅当它们的长度不同,或者它们在某个对应位置上的字符不相同(即只对比提取出的字符构成的字符串本身是否一致)。
**输入格式**
第一行包含一个整数 $T$($1 \le T \le 10^6$),表示测试用例数。
对于每组测试用例:
第一行包含两个整数 $n, k$($1 \le n \le 10^6, 0 \le k \le n$)。
第二行包含一个长度为 $n$ 的字符串 $S$,保证仅包含小写字母。
保证所有测试用例的 $\sum n \le 10^6$。
**输出格式**
对于每组测试用例,输出一行一个整数,表示本质不同的非空 $k$-松散子序列的数量对 $998244353$ 取模的结果。
**样例**
```
输入:
3
4 1
aabb
5 2
abcab
7 3
abcdece
输出:
3
6
10
```
**样例解释**
- 对于第一个测试用例($S = \text{aabb}$,$k = 1$),下标位置差必须严格大于 $1$。满足条件的本质不同的子序列有 `a`、`b`、`ab`。
- 对于第二个测试用例($S = \text{abcab}$,$k = 2$),下标位置差必须严格大于 $2$。满足条件的本质不同的子序列有 `a`、`b`、`c`、`aa`、`ab`、`bb`。
## 思路讲解
::: gemini 的这个思路
### 题目描述
给定一个长度为 $n$、仅由小写字母组成的字符串 $S$ 以及一个非负整数 $k$。
需要计算 $S$ 的本质不同的非空 $k$-松散子序列的数量,并将结果对 $998244353$ 取模。
- $k$**-松散子序列**:如果子序列在原字符串 $S$ 中对应的下标序列为 $pos_1, pos_2, \dots, pos_m$,且满足对于所有的 $i \in [1, m-1]$,都有 $pos_{i+1} - pos_i > k$,则该子序列为 $k$-松散子序列。即相邻选择的字符在原串中的距离必须严格大于 $k$。
- **本质不同**:两个子序列被认为是不同的,当且仅当它们作为字符串本身不一致,或者长度不同。
### 算法思路
本题可以使用动态规划来解决。
为了避免重复计算本质相同的子序列,我们可以采用**贪心匹配**的思想:对于任何一个合法的子序列,为了给后续字符留下最大的选择空间,我们总是贪心地在原串中寻找它的第一个可用匹配位置。在这个约束下,每个合法的 $k$-松散子序列都唯一对应原串中的一种提取方式。
我们定义 $V_x$ 为:在后缀 $S_{x \dots n}$ 中,能够选出的本质不同的合法序列数量(第一步选择没有 $+k$ 的位置限制,但后续的选择仍需满足距离 $>k$ 的限制)。
考虑如何从 $V_{x+1}$ 转移到 $V_x$:
与后缀 $S_{x+1 \dots n}$ 相比,后缀 $S_{x \dots n}$ 多了一个字符 $S_x$ 可以作为序列的开头。
1. 如果我们将 $S_x$ 作为子序列的第一个字符,那么下一个字符必须从下标 $\ge x+k+1$ 的位置开始选择。这种情况能产生的合法子序列数量为 $1 + V_{x+k+1}$(其中 $1$ 代表仅由 $S_x$ 构成的长度为 $1$ 的子序列)。
1. 然而,在 $V_{x+1}$ 的结果中,可能已经包含了以 $S_x$ 这个字符开头的序列——它们是把 $S_x$ 的下一次出现位置(记为 $nxt_x$)作为起点的。为了防止重复计算以该字符开头的序列,我们需要把这部分重复的序列减去。以 $nxt_x$ 作为起点能产生的子序列数量为 $1 + V_{nxt_x+k+1}$。
综上所述,我们可以得出状态转移方程。
定义辅助数组 $W_x$ 表示选择位置 $x$ 作为开头时的组合数:
如果 $x \le n$,则 $W_x \leftarrow 1 + V_{x+k+1}$;否则 $W_x \leftarrow 0$。
那么状态转移方程为:
$V_x \leftarrow (V_{x+1} + W_x - W_{nxt_x} \pmod{998244353} + 998244353) \bmod 998244353$
我们只需从右向左($x$ 从 $n$ 递减到 $1$)遍历字符串计算 $V_x$,最终的答案即为 $V_1$。
### 代码实现
```cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MOD = 998244353;
void solve() {
int n, k;
if (!(cin >> n >> k)) return;
string s;
cin >> s;
// nxt[i] 记录字符 s[i-1] 在位置 i 之后第一次出现的下标(1-indexed)
vector<int> nxt(n + 1, n + 1);
vector<int> last_seen(26, n + 1);
for (int i = n; i >= 1; --i) {
int c = s[i - 1] - 'a';
nxt[i] = last_seen[c];
last_seen[c] = i;
}
// V[i] 记录在后缀 s[i...n] 中本质不同的合法子序列数量
// 数组大小开到 n + k + 5 以防止越界访问
vector<int> V(n + k + 5, 0);
for (int i = n; i >= 1; --i) {
// 如果选择当前的字符,后续的合法序列数量加上它本身(1)
int w_i = V[i + k + 1] + 1;
if (w_i == MOD) w_i = 0;
// 如果该字符在之后还出现过,需要减去在下一次出现位置处选择该字符所产生的情况
int w_nxt = 0;
if (nxt[i] <= n) {
w_nxt = V[nxt[i] + k + 1] + 1;
if (w_nxt == MOD) w_nxt = 0;
}
// 状态转移:V[i] = V[i + 1] + w_i - w_nxt
int v = V[i + 1] + w_i;
if (v >= MOD) v -= MOD;
v -= w_nxt;
if (v < 0) v += MOD;
V[i] = v;
}
cout << V[1] << "\\n";
}
int main() {
// 优化输入输出流速度
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
if (cin >> t) {
while (t--) {
solve();
}
}
return 0;
}
```
### 复杂度分析与边界情况
**算法说明**:
我们利用了子序列自动机的贪心匹配性质,将“本质不同”的限制转换为“每次必须选取该字符第一次出现的位置”。接着使用动态规划,通过类似于经典本质不同子序列计数(即 $k=0$ 时)的加减容斥思想,巧妙避开了状态中带有位置距离限制的遍历,将每一次状态转移做到了 $O(1)$ 的极致效率。
**时间复杂度**:
1. 预处理 `nxt` 数组需要逆序遍历一次字符串,花费 $O(n)$ 的时间。
1. 动态规划过程只需要从后向前遍历一次,每次循环内部都是简单的条件判断和常数级别的加减运算,花费 $O(n)$ 的时间。
因此对于每组测试用例,时间复杂度为 $O(n)$。所有测试用例的总时间复杂度为 $O(\sum n)$,最大计算量约 $10^6$ 次操作,可以在 $1$ 秒的时间限制内极其轻松地通过。
**空间复杂度**:
我们创建了长度为 $n+1$ 的 `nxt` 数组,以及长度为 $n+k+5$ 的动态规划数组 `V`。两个数组的大小均为 $O(n)$ 级别。
由于每次都是动态分配,空间复杂度为 $O(n)$。最大极限情况下占用内存不足 $15\text{MB}$,严格符合并远低于 $512\text{MB}$ 的内存限制要求。
**边界情况处理**:
1. $k \ge n$:此时任何选取的字符下标加上 $k+1$ 都会超出字符串长度,即 $V_{i+k+1}$ 必然为 $0$。此时原串中每种出现过的字符只会被单独算作一个长度为 $1$ 的子序列(由于 $W_{nxt_x}$ 的减法抵消作用,每个不同的字母只会全局计算一次)。代码中分配的空间 `n + k + 5` 完美覆盖了这一情况,不仅逻辑正确也不会出现数组越界。
1. **取模运算的负数情况**:由于状态转移中含有减法(容斥),直接取模可能会导致负数结果传递。代码中采用了加减法与判断结合的方式(`v -= w_nxt; if (v < 0) v += MOD;`)手动修正负数。这种方式不仅避免了除法取模运算符 `%` 带来的指令周期损耗,还确保了最终状态值绝对正确且总是正整数。
:::
呃,这个我们需要想办法做到**求本质不同的这个所有子序列**。
我们转移的时候,就是应该以 s[i] 开头的串,在我们所有的这个的计数之中,应该以 s[i] 开头的串只应该真的以 i 开头的时候被计算,因此后面的应该被减去。(当然,我们是从后往前遍历)
具体而言,这个转移式子是:
$$
next[i] 存在:\ dp[i]\gets 2\times dp[i+1]-(dp[next[i]+1]+1)+1 \\
dp[i]\gets 2\times dp[i+1]-dp[next[i]+1] \\
next[i] 不存在:\ dp[i]\gets 2\times dp[i+1]+1
$$
注意,为什么是减去 $dp[next[i]+1]+1$ 呢?因为其实这个才是含有 $next[i]$ 的子序列的所有数量。
当然,这个是求本质不同的这个子序列的时候,我们要计算 k-松散子序列。
计算 k-松散子序列:
$$
next[i] 不存在:\ dp[i]\gets 2\times dp[i+k+1]+1 \\
next[i] 存在:\ dp[i]\gets 2\times dp[i+k+1]+1-(dp[next[i]+k+1]+1) \\
dp[i]\gets 2\times dp[i+k+1]-dp[next[i]+k+1]
$$
## AC代码
::: 源代码
```cpp
```
:::
## 心路历程(WA,TLE,MLE……)