AT_abc359_d [ABC359D] Avoid K Palindrome

题目描述

给定一个由 A、B、? 组成的长度为 $N$ 的字符串 $S$。

给定一个正整数 $K$。如果一个仅由 A、B 组成的字符串 $T$ 满足以下条件，则称 $T$ 为好字符串：

• $T$ 的任意长度为 $K$ 的连续子串中，都不存在回文串。

设 $S$ 中包含 $q$ 个 ?。将这 $q$ 个 ? 分别替换为 A 或 B，一共可以得到 $2^q$ 种不同的字符串。请你求出其中有多少种是好字符串。

由于答案可能非常大，请输出答案对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$ $S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

7 4
AB?A?BA

输出 #1

1

输入输出样例 #2

输入 #2

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

输出 #2

116295436

输入输出样例 #3

输入 #3

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

输出 #3

0

输入输出样例 #4

输入 #4

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

输出 #4

259240

说明/提示

限制条件

• $2 \leq K \leq N \leq 1000$
• $K \leq 10$
• $S$ 由 A、B、? 组成
• $S$ 的长度为 $N$
• $N,K$ 均为整数

样例解释 1

给定的字符串中有 $2$ 个 ?。将这 $2$ 个 ? 分别替换为 A 或 B，一共可以得到如下 $4$ 种字符串：

• ABAAABA
• ABAABBA
• ABBAABA
• ABBABBA 其中，除了第一个 ABAAABA，其余 $3$ 个字符串都包含长度为 $4$ 的回文子串 ABBA，因此不是好字符串。故输出 1。

样例解释 2

请注意，要求输出好字符串的个数对 $998244353$ 取模的结果。

样例解释 3

也有可能无论如何替换 ? 都无法得到好字符串。

由 ChatGPT 4.1 翻译