ARC089D ColoringBalls

kcn999 · 2021-10-07 21:24:09 · 题解

这个题是求颜色序列的方案数，一种颜色序列可能由多种操作序列映射得到。

考虑序列 \color{red}\bullet\color{blue}\bullet\color{red}\bullet\color{blue}\bullet\color{red}\bullet 可能有两种构造方式：

按照这个思路，手玩一下可以发现，若一段红蓝交错的颜色序列中有 k 段蓝色（k\ge1），则最少可以用 k+1 次操作构造出来，且前两步必为 \color{red}\texttt r \color{blue}\texttt b，后面的操作可以是 \color{red}\texttt r 也可以是 \color{blue}\texttt b。当然，如果要构造一段纯红的颜色序列，则只需要一步 \color{red}\texttt r 即可。

这题有长度 n 的限制，有操作序列长度 k 的限制，还有操作顺序的限制，直接计算的话就会很麻烦。

发现一个操作序列映射到的是颜色段序列，也就是说我们可以把每个颜色段缩成一个颜色点，求出颜色点序列的方案数之后，再乘一些组合系数就可以得到颜色段序列的方案数。这样我们就可以先忽略掉 n 的限制。

颜色点序列一定是若干个红色序列或红蓝序列，被若干个黑色序列分隔开来。

此时给你操作序列 s，若要生成 x 个红蓝序列，y 个红色序列，可以贪心地先把 s 中最先出现的 x 个 \color{red}\texttt r 分配给 x 个红蓝序列，再把后面的 y 个 \color{red}\texttt r 分配给 y 个红色序列。分配完之后，又因为构造红蓝序列需要先选一次 \color{blue}\texttt b 才能任选两种操作，所以先出现的 \color{blue}\texttt b 也要尽可能分配。

如果不能按照上述方案分配 \color{red}\texttt r\color{black},\color{blue}\texttt b，显然一定无法构造出 x 个红蓝序列、y 个红色序列。

如果可以分配，就把提前分配出去的 \color{red}\texttt r\color{black},\color{blue}\texttt b 从 s 中删去。

我们只要确定了 x 个红蓝序列的排列顺序，直接用插板法把 y 个红色序列插进去即可，方案数为 \dbinom{x+y}{y}。所以我们只用考虑如何计算 x 个红蓝序列的排列方案数。

然而还需要考虑构造这 x 个红蓝序列的先后顺序。

设 \mathrm{cnt}_i 表示第 i 个红蓝序列的蓝色点个数（注意已经把段缩成了点），设 \mathrm{sum}_i 表示提前分配了第 i 段的 \color{blue}\texttt b 后，此时这个 \color{blue}\texttt b 在 s 中的位置 p_i 后面剩下多少个可选操作（即设被分配给 i 的 \color{blue}\texttt b 的位置为 p_i，\mathrm{sum}_i 即为 s_{p_i},s_{p_i+1},\cdots,s_k 在删去提前分配的操作后，未被删除的操作个数）。

则需要满足 \forall i \in [1,x],\mathrm{sum}_i\ge\sum_{j = i}^x(\mathrm{cnt}_j-1)。

显然令 \forall i \in [1,x),\mathrm{cnt}_i \ge \mathrm{cnt}_{i+1} 更优。

那么就可以考虑 DP 了。

设 f(i,j,k) 表示考虑到颜色序列 [i,x]，此时 j = \sum_{j = i}^x(\mathrm{cnt}_j-1),k = \mathrm{cnt}_i - 1 的方案数。

则

观察这个式子，直接转移是 O(n^4 \log n) 的，前缀和优化一下即可做到 O(n^3\log n)。

至于 \mathrm{sum}_i，在判断能否分配时顺便预处理出来即可。

分出 x 个红蓝序列的方案数为 f(1,j,k)。

现在考虑还原颜色段序列，即相当于要在每个点填充若干个元素，其中某些点可以填 0 个，而有些点不行。

首先每段红蓝序列都有 2 个边缘的 \color{red}\bullet 可以填 0 个（构造 \color{red}\bullet\color{blue}\bullet\color{red}\bullet\color{blue}\bullet\color{red}\bullet 和构造 \color{blue}\bullet\color{blue}\bullet\color{red}\bullet\color{blue}\bullet\color{blue}\bullet 的方案是相等的），然后整个颜色段序列都有 2 个边缘的 \color{black}\bullet 可以填 0 个。（可以被 \color{red}\bullet\color{black}/\color{blue}\bullet 覆盖），故可以为空的个数为 2x+2。

红蓝序列共有 3x+2j 个点，红色序列共有 y 个点，减去上述的 2x 个点，则有 x+2j+y 个点至少要填 1。又有 x+y-1 个黑色序列要用于隔开红蓝序列和红色序列，它们也至少要填 1。所以共有 2x+2j+2y-1 个点至少要填 1。

综上得到 f(1,j,y) 对答案的贡献为 f(1,j,y)\cdot \dbinom{x+y}y\cdot\dbinom{n+2x+1}{4x+2y+2j}。

算上枚举 x,y 的时间，总时间复杂度为 O(n^5 \log n)。但是常数很小，足够通过本题。

注意枚举 l 的时候要判断 \mathrm{sum}_{i+l}\ge j - kl，如果不满足那后面的 l 一定不合法，直接终止循环即可。

#include <bits/stdc++.h>
#define MAX_N (70 + 5)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int n, m;
char s[MAX_N];
bool vis[MAX_N];
int sum[MAX_N];
int f[MAX_N][MAX_N][MAX_N];
int C[505][505];
bool Init(int x, int y) {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= m; ++i) {
        if (s[i] == 'r') {
            if (cnt1 < x + y) ++cnt1, vis[i] = 0;
            else vis[i] = 1;
        }
        else {
            if (cnt2 < x && cnt1 > cnt2) ++cnt2, vis[i] = 0;
            else vis[i] = 1;
        }
    }
    if (cnt1 < x + y || cnt2 < x) return false;
    int tmp = 0, cur = x;
    for (int i = m; i; --i) {
        if (vis[i]) ++tmp;
        else if (s[i] == 'b') sum[cur--] = tmp;
    }
    return true;
}
int main() {
    n = 500;
    for (int i = 0; i <= n; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) 
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    scanf("%d%d%s", &n, &m, s + 1);
    int ans = 0;
    for (int x = 0; x <= m; ++x) {
        for (int y = 0; 2 * x + y <= m; ++y) {
            if (!Init(x, y)) break;
            int len = sum[1];
            for (int i = 0; i <= len; ++i)
                f[x + 1][0][i] = 1;
            for (int i = x; i; --i) {
                for (int k = 0; k <= len; ++k)
                    f[i][0][k] = 1;
                for (int j = 1; j <= sum[i] && 2 * j + 2 * x + 2 * y - 1 <= n; ++j) {
                    for (int k = 1; k <= len; ++k) {
                        for (int l = 1; i + l <= x + 1 && j - k * l >= 0 && j - k * l <= sum[i + l]; ++l) 
                            f[i][j][k] = (f[i][j][k] + (ll)f[i + l][j - k * l][k - 1] * C[x - i + 1][l]) % mod;
                        f[i][j][k] = (f[i][j][k] + f[i][j][k - 1]) % mod;
                    }
                }   
            }
            int res = 0;
            for (int j = 0; j <= len && 2 * j + 2 * x + 2 * y - 1 <= n; ++j)
                res = (res + (ll)f[1][j][len] * C[n + 2 * x + 1][4 * x + 2 * y + 2 * j]) % mod;
            res = (ll)res * C[x + y][y] % mod;
            ans = (ans + res) % mod;
            for (int i = 0; i <= len; ++i)
                f[x + 1][0][i] = 0;
            for (int i = x; i; --i) 
                for (int j = 0; j <= sum[i]; ++j)
                    for (int k = 0; k <= len; ++k) 
                        f[i][j][k] = 0;
            for (int i = 1; i <= x + y; ++i)
                sum[i] = vis[i] = 0;
        }
    }
    ans = (ans + mod) % mod;
    printf("%d", ans);
    return 0;
}