#2017. Imbalance

    ID: 2017 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest754来源:qoj.ac数据:公开样例动态规划

Imbalance

Imbalance

题目描述

标题: Imbalance - Problem - QOJ.ac

#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≤m+1≤k≤n≤114 且 k 是偶数。

子任务编号n≤特殊性质分值子任务依赖120102114k≤201013663014114m=0205114302,3,4

**时间限制:**2s

**空间限制:**1GB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 4 2
01
3

样例 2

13 6 0
996