← 返回题目列表

Codeforces · 1622/D

D. 随机播放

中文机器翻译题面 查看原题

给定一个二进制字符串(即由字符 0 和/或 1 组成的字符串)$$$s$$$,长度为 $$$n$$$。您最多可以对字符串 $$$s$$$ 执行以下操作:选择 $$$s$$$ 中恰好包含 $$$k$$$ 个字符 1 的子字符串(连续子序列),然后将其打乱(根据需要对子字符串中的字符重新排序)。

计算最多执行一次此操作从 $$$s$$$ 中可以获得的不同字符串的数量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 5000$$$; $$$0 \le k \le n$$$)。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 0 和/或 1 组成。

输出

打印一个整数——最多执行一次所描述的操作从$$$s$$$中获得的不同字符串的数量。由于答案可能很大,因此输出它对 $$$998244353$$$ 取模。

示例

输入 #1

7 2
1100110

输出 #1

16

输入 #2

5 0
10010

输出 #2

1

输入 #3

8 1
10001000

输出 #3

10

输入#4

10 8
0010011000

输出#4

1

注意

您可以在第一个示例中获取一些字符串:

- 要获得0110110,可以取出从$$$1$$$-第一个字符到第$$$4$$$-个字符的子串,即1100,并将其字符重新排序,得到0110;
- 要获得1111000,可以取出从$$$3$$$第一个字符到第$$$7$$$个字符的子字符串,即00110,并将其字符重新排序,得到11000;
- 要获得 1100101,您可以取出从第 $$$5$$$ 字符到第 $$$7$$$ 字符的子字符串,即 110,并将其字符重新排序以获得 101。

在第二个示例中,$$$k = 0$$$,因此您只能选择仅由 0 个字符组成的子字符串。对它们重新排序根本不会改变字符串,因此您可以获得的唯一字符串是 10010。