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$
输出格式
请输出答案。
说明/提示
### 限制条件
- $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 翻译