← 返回题目列表

AtCoder · abc359_d

G. 避免 K 回文

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

分数: 450 点

问题陈述

给你一个字符串 S 长度 N 由字符组成 A, B,和 ?.

还给你一个正整数 K。 一个字符串 T 组成 A 和 B 被认为是 好字符串 如果满足以下条件:

  • No 长度连续的子串 K in T 是一个回文。

让 q 是数量 ? 中的字符 S。 有 2^q 可以通过替换每个字符串来获得 ? in S 与任一 A or B。找出这些字符串中有多少是好字符串。

计数可能非常大,因此求模 998244353.

约束

  • 2 \leq K \leq N \leq 1000
  • K \leq 10
  • S 是一个由以下组成的字符串 A, B,和 ?.
  • 的长度 S is N.
  • N 和 K 是整数。

输入

输入由标准输入按以下格式给出:

N K
S

输出

打印答案。


示例输入 1

7 4
AB?A?BA

示例输出 1

1

给定的字符串有两个 ?s。 分别替换得到四个字符串 ? 与 A or B:

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

其中,最后三个包含连续的子字符串 ABBA 的长度为 4,这是一个回文,因此不是好的字符串。

因此,您应该打印 1.


示例输入 2

40 7
????????????????????????????????????????

示例输出 2

116295436

确保找到好字符串的模数 998244353.


示例输入 3

15 5
ABABA??????????

示例输出 3

0

可能没有办法更换 ?s 获得一个好的字符串。


示例输入 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

示例输出 4

259240