自动搬运

查看原文

来自洛谷，原作者为

	Elma_ blog：https://www.cnblogs.com/came11ia

搬运于2025-08-24 22:34:46，当前版本为作者最后更新于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$ 时，新划分出的这一段对权值没有贡献，转移如下：

$$f_{i,j,0}= \sum_{k=p_i}^{i-1} f_{k,j,1}$$

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

$$f_{i,j,0} = \sum_{k=i-m+1}^{i-1}f_{k,j,1}+\sum_{k=p_i}^{i-m}f_{k,j-[(i-k)-m+1],1} $$

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

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

$$j - [(i-k)-m+1]-k = j - i + m - 1$$

而这个东西和 $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;
}