Avoid K Palindrome

题目描述

给你一个长度为 $N$ 的字符串 $S$，由字符 $A$、$B$ 和 $?$ 构成。 还给你一个正整数 $K$。 一个由 $A$ 和 $B$ 构成的字符串 $T$ 被认为是一个 好字符串，如果它满足以下条件：

在 $T$ 中没有任何长度为 $K$ 的连续子串是回文。

令 $q$ 为 $S$ 中字符 $?$ 的个数。 通过将 $S$ 中的每个 $?$ 替换为 $A$ 或 $B$，可以得到 $2^q$ 个字符串。求这些字符串中有多少个是好字符串。 计数可能非常大，所以结果请对 $998244353$ 取模。

输入格式

输入从标准输入给出，格式如下： $N$ $K$ $S$

输出格式

输出答案。

7 4
AB?A?BA

1

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

116295436

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

0

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

259240

提示

$2 \leq K \leq N \leq 1000$ $K \leq 10$ $S$ 是由 $A$、$B$ 和 $?$ 构成的字符串。 $S$ 的长度为 $N$。 $N$ 和 $K$ 是整数。给定字符串有两个 $?$。 将每个 $?$ 替换为 $A$ 或 $B$ 可以得到四个字符串：

$ABAAABA$ $ABAABBA$ $ABBAABA$ $ABBABBA$

其中后三个都包含长度为 4 的连续子串 $ABBA$，这是一个回文，因此不是好字符串。 因此，你应该输出 $1$.
请确保对 $998244353$ 取模后输出好字符串的数量。
也有可能不存在将 $?$ 替换后得到好字符串的办法。

标签: AtCoder|abc359D

来源

AtCoder|abc359D