1454 : 松散子序列

时间限制Time Limit 1 秒Sec 内存限制Memory Limit 256 兆MB 提交次数Submitted 128 次Times 通过次数Solved 60 次Times

标准评测 Standard

从标准输入读入，结果写到标准输出。评测将输出拆成 token，与标准答案逐项比较，不按整段逐字节比对。 Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.

比对Compare	token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored.
不同则错Differs	token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ.
输入Input	标准输入，格式见题面。Standard input; format as in the statement.
输出Output	标准输出。Standard output.

模板Template

C++ C Java Python

#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    cout << (a + b) << endl;
    return 0;
}

#include <stdio.h>
int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        System.out.println(a + b);
    }
}

a, b = map(int, input().split())
print(a + b)

题目描述Description

给定一个长度为 n 且仅由小写字母组成的字符串 S，并做出如下约定。

子序列：从 S 中将若干元素（不一定连续）提取出来而不改变相对位置形成的序列称为子序列。
k 松散子序列：若 S 的一个子序列中任意两个相邻字符在原串 S 中至少间隔 k 个位置，则这个子序列称为 S 的一个 k 松散子序列。具体地，对于 S 的一个长为 m 的子序列 T = \overline{S_{pos_{1}}S_{pos_{2}}\cdots S_{pos_{m}}}，T 是 S 的一个 k 松散序列当且仅当 \forall i \in [1, m - 1]，pos_{i + 1} - pos_{i} > k。

现给定一个非负整数 k，你需要求出 S 本质不同的非空 k 松散子序列数目，对 998244353 取模的结果。

称 S 的两个子序列 A 与 B 本质不同，当且仅当 |A| \neq |B| 或存在下标 i 满足 A_i \neq B_i。

输入格式Input

第一行一个整数 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。

输出格式Output

对于每组数据，输出一行一个整数，代表 S 本质不同的非空 k 松散子序列数目，对 998244353 取模。

样例Sample

提示Hint

对于第一组数据，子序列 a͡，b͡，a͡b 符合要求。

对于第二组数据，子序列 a͡，b͡，c͡，a͡a，a͡b，b͡b 符合要求。

出题Author

UESTC

来源Source

广东省第二十二届大学生程序设计竞赛（GDCPC2025）