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。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）