#P18611. Distinct Subsequences
Distinct Subsequences
Distinct Subsequences
给定一个长度为n的二进制字符串s和一个整数k。请计算s中长度恰为k的不同子序列数量,答案对998244353取模。
子序列由按原顺序选取若干字符得到,所选位置不要求连续。“不同”按得到的字符串内容区分;同一个字符串即使能用多种下标选择得到,也只计算一次。
输入格式
第一行两个整数n、k。第二行一个长度为n、只含0和1的字符串s。本题只有一个测试用例。
输出格式
输出一个整数,为长度恰为k的不同子序列数量对998244353取模的结果。
数据范围
1<=k<=n<=200000。
样例输入 1
5 3
00110
样例输出 1
5
样例输入 2
12 8
000111000000
样例输出 2
12
样例输入 3
31 12
1110100111110110101111010100010
样例输出 3
3985