题目描述
定义一个 01 串是平衡的当且仅当它的 01 个数相同。
现在给定 n,k 和一个长度为 m 的 01 串 S,求有多少长度为 n 且以 S 为前缀的 01 串满足其不存在长度为 k 的平衡子串,对 998244353 取模。
输入格式
一行,两个整数 n,k 和 m 表示串的长度,平衡串的限制和 S 的长度。
接下来一行一个长度为 m 的 01 串表示 S。
输出格式
一行一个整数,表示答案模 998244353 后的结果。
样例一
input
5 4 2
01
output
3
样例二
input
13 6 0
(此处一个空行)
output
996
数据规模与约定
对于 100% 的数据,保证 1≤m+1≤k≤n≤114 且 k 是偶数。
子任务编号 | n≤ | 特殊性质 | 分值 | 子任务依赖 |
---|---|---|---|---|
1 | 20 | 10 | ||
2 | 114 | k≤20 | 10 | 1 |
3 | 66 | 30 | 1 | |
4 | 114 | m=0 | 20 | |
5 | 114 | 30 | 2,3,4 |
时间限制:2s
空间限制:1GB