题目描述

难度分:$1381$

输入$n$、$k(2 \leq k \leq n \leq 1000$且$k \leq 10)$和长为$n$的字符串$s$，只包含A、B、?三种字符。

如果一个字符串不包含长度恰好为$k$的回文子串，我们称其为合法字符串。

把$s$中的所有?替换成A或B，可以得到$2^q$个不同的字符串，其中 $q$是$s$中的?的个数。

输出这$2^q$个字符串中的合法字符串个数，模$998244353$。

输入样例$1$

7 4
AB?A?BA

输出样例$1$

1

输入样例$2$

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

输出样例$2$

116295436

输入样例$3$

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

输出样例$3$

0

输入样例$4$

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

输出样例$4$

259240

算法

这样的计数题目一般不是DP就是组合数学，但是看到数据范围这么小，可以往DP上考虑。

状压DP。

假设A是二进制$0$，B是二进制$1$。

状态定义

$f[i][mask]$表示当前要考虑第$i$个位置，前缀$[1,i)$已经填完，最后$k-1$个字母是$mask$的情况下（$mask$的高位表示排在后面的字母，低位表示排在前面的字母），能够得到多少个合法串。

状态转移

分为以下两种情况：

1. 如果$s[i] \neq$A，那么当前位置就要填B，应该把原来$[1,i-1]$的$mask$状态去掉最低位（因为最低位是最远的，用右移就可以实现），然后在最高位或上一个$1$，当$i \lt k$长度不够或$mask+2^{k-1}$不是回文串时进行状态转移，状态转移方程为$f[i][\lfloor \frac{mask}{2} \rfloor+2^{k-2}]+=f[i-1][mask]$。
2. 如果$s[i] \neq$B，那么当前位置就要填A，应该把原来$[1,i-1]$的$mask$状态去掉最低位（因为最低位是最远的，用右移就可以实现），然后在最高位或上一个$0$，相当于什么也没干。当$i \lt k$长度不够或$mask$不是回文串时进行状态转移，状态转移方程为$f[i][\lfloor \frac{mask}{2} \rfloor]+=f[i-1][mask]$。

最后的答案就是$\Sigma_{mask \in [0,2^{k-1})}f[n][mask]$，遍历一下$n$长度的串最后$k-1$个字母的状态，累加起来即可。

复杂度分析

时间复杂度

遍历$i \in [1,n]$时间复杂度为$O(n)$，遍历$mask$时间复杂度为$O(2^k)$，检查$mask$是不是长度为$k$的回文时间复杂度为$O(k)$。单次转移的时间复杂度为$O(1)$，因此算法整体的时间复杂度为$O(nk2^k)$。

空间复杂度

空间瓶颈在于DP矩阵$f$，状态数量为$O(n2^k)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 1001, K = 11, MOD = 998244353;
int n, k, f[N][1<<K];
char s[N];

bool ispalindrome(int mask) {
    int l = 0, r = k - 1;
    while(l < r) {
        if((mask>>l&1)^(mask>>r&1)) return false;
        l++, r--;
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    // 初始化第1个位置的状态
    if(s[1] != 'A') f[1][1<<k - 2] = 1;
    if(s[1] != 'B') f[1][0] = 1;
    // 递推
    for(int i = 2; i <= n; i++) {
        for(int mask = 0; mask < (1<<k - 1); mask++) {
            if(s[i] != 'A' && (i < k || !ispalindrome(mask|(1<<k - 1)))) {
                // i位置是B
                f[i][mask>>1|(1<<k - 2)] = (f[i][mask>>1|(1<<k - 2)] + f[i - 1][mask]) % MOD;
            }
            if(s[i] != 'B' && (i < k || !ispalindrome(mask))) {
                // i位置是A
                f[i][mask>>1] = (f[i][mask>>1] + f[i - 1][mask]) % MOD;
            }
        }
    }
    int ans = 0;
    for(int mask = 0; mask < (1<<k - 1); mask++) {
        ans = (ans + f[n][mask]) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}