The 2025 Jiangsu Collegiate Programming Contest（2025 江苏省赛）——H. Loose Subsequences（求本质不同子序列的方法）

题目大意

题目描述
给定一个长度为 $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$ 可以作为序列的开头。

如果我们将 $S_x$ 作为子序列的第一个字符，那么下一个字符必须从下标 $\ge x+k+1$ 的位置开始选择。这种情况能产生的合法子序列数量为 $1 + V_{x+k+1}$ （其中 $1$ 代表仅由 $S_x$ 构成的长度为 $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$ 。

代码实现

#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)$ 的极致效率。
时间复杂度：

预处理 nxt 数组需要逆序遍历一次字符串，花费 $O(n)$ 的时间。
动态规划过程只需要从后向前遍历一次，每次循环内部都是简单的条件判断和常数级别的加减运算，花费 $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}$ 的内存限制要求。
边界情况处理：
$k \ge n$ ：此时任何选取的字符下标加上 $k+1$ 都会超出字符串长度，即 $V_{i+k+1}$ 必然为 $0$ 。此时原串中每种出现过的字符只会被单独算作一个长度为 $1$ 的子序列（由于 $W_{nxt_x}$ 的减法抵消作用，每个不同的字母只会全局计算一次）。代码中分配的空间 n + k + 5 完美覆盖了这一情况，不仅逻辑正确也不会出现数组越界。
取模运算的负数情况：由于状态转移中含有减法（容斥），直接取模可能会导致负数结果传递。代码中采用了加减法与判断结合的方式（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代码

源代码

Znzryb's Blog