QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 4893. Imbalance

Statistics

题目描述

定义一个 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\le m+1\le k\le n\le 114$ 且 $k$ 是偶数。

子任务编号$n\le$特殊性质分值子任务依赖
$1$$20$$10$
$2$$114$$k\le 20$$10$$1$
$3$$66$$30$$1$
$4$$114$$m=0$$20$
$5$$114$$30$$2,3,4$

时间限制:$\rm 2s$

空间限制:$\rm 1GB$