题解 P7969 【[KSN2021] Self Defence】

Elma_ · 2021-11-26 20:49:49 · 题解

难得一见的 CNOI 风巨大套路题。

设 f_{i,j,0/1} 为填了前 i 个字符，此时字符串权值为 j，第 i 个字符是 A/B 的方案数。

转移时枚举上一个连续段的结尾 k 进行转移，我们以第 i 个字符为 A 的情况为例，设上一个 B 出现的位置为 p_i，不难发现合法的 k 满足 k \in [p_i,i-1]。分类讨论：

• 当 i - p_i < m 时，新划分出的这一段对权值没有贡献，转移如下：

• 当 i - p_i \geq m 时，我们将对权值有贡献的部分和对权值没有贡献的部分分两段进行转移。对于一个长为 l(l \geq m) 的连续段，其对权值的贡献为 l-m+1。因此转移如下：

第 i 个字符为 B 的情况同理。边界 f_{0,0,0/1} =1。然而这样是 O(n^3) 的，我们还得想办法优化上面的东西。

对于对权值没有贡献的部分用前缀和优化即可。比较棘手的是对权值有贡献的部分。我们观察一下转移时用到的状态的两个下标 i,j 之差：

而这个东西和 k 是无关的。这启发我们多设一个 h_{i,k,0/1} 表示前 i 位中，所有 j-i = k 的 f_{i,j,0/1} 之和，前缀和搞一下就能做到 O(n^2) 了。边界 g_{0,0,0/1}=h_{0,0,0/1}= 1。

然后需要注意的是 j-i 可能减出负数，我们把下标平移 n 就可以避免这个问题了。

const int MN = 3e3 + 5, Mod = 1e9 + 7;

int N, M, K, f[MN][MN][2], g[MN][MN][2], h[MN][2 * MN][2], pA[MN], pB[MN];
char s[MN];

signed main(void) {
    N = read(), M = read(), K = read(), scanf("%s", s + 1);
    for (int i = 1, A = 0, B = 0; i <= N; i++) {
        if (s[i] == 'A') A = i;
        if (s[i] == 'B') B = i;
        pA[i] = A, pB[i] = B;
    }
    g[0][0][0] = g[0][0][1] = h[0][N][0] = h[0][N][1] = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            if (s[i] != 'B') {
                if (i - pB[i] < M) {
                    f[i][j][0] = (f[i][j][0] + ((g[i - 1][j][1] - (pB[i] ? g[pB[i] - 1][j][1] : 0)) % Mod + Mod) % Mod) % Mod;
                } else {
                    int x = j - i + M - 1 + N;
                    f[i][j][0] = (f[i][j][0] + ((g[i - 1][j][1] - g[i - M][j][1]) % Mod + Mod) % Mod) % Mod;
                    f[i][j][0] = (f[i][j][0] + ((h[i - M][x][1] - (pB[i] ? h[pB[i] - 1][x][1] : 0)) % Mod + Mod) % Mod) % Mod;
                }
            }
            if (s[i] != 'A') {
                if (i - pA[i] < M) {
                    f[i][j][1] = (f[i][j][1] + ((g[i - 1][j][0] - (pA[i] ? g[pA[i] - 1][j][0] : 0)) % Mod + Mod) % Mod) % Mod;
                } else {
                    int x = j - i + M - 1 + N;
                    f[i][j][1] = (f[i][j][1] + ((g[i - 1][j][0] - g[i - M][j][0]) % Mod + Mod) % Mod) % Mod;
                    f[i][j][1] = (f[i][j][1] + ((h[i - M][x][0] - (pA[i] ? h[pA[i] - 1][x][0] : 0)) % Mod + Mod) % Mod) % Mod;
                }
            }
            g[i][j][0] = (g[i - 1][j][0] + f[i][j][0]) % Mod;
            g[i][j][1] = (g[i - 1][j][1] + f[i][j][1]) % Mod;
            h[i][j - i + N][0] = (h[i - 1][j - i + N][0] + f[i][j][0]) % Mod;
            h[i][j - i + N][1] = (h[i - 1][j - i + N][1] + f[i][j][1]) % Mod;
        }
    }
    int Ans = 0;
    Ans = (f[N][K][0] + f[N][K][1]) % Mod;
    printf("%d\n", Ans);
    return 0;
}