Visits: 444

ARC089F ColoringBalls

题意

• 有 $n$ 个白色小球排成一排。
• 给定一个长度为 $k$ 的只包含红色和蓝色的染色操作序列。
• 按照染色操作序列的顺序，每次选择一段区间（可以为空），将区间内的小球全部染成当前颜色。
• 另外，要求整个过程中不存在把白色小球染成蓝色的情况，即当染成蓝色时，选择的区间内不能包含白色小球。
• 求最终可以染出多少个不同的小球颜色序列。
• $n,k \le 70$，答案对 $10^9+7$ 取模。

题解

考虑一个暴力做法：枚举最终的小球颜色序列，判断是否合法。

考虑如何判断，以 BRBRBWRRBRBBWWRRRRWRBBWWRRBBBR 为例：

• 首先显然可以先进行一次 unique 而不影响答案，即变成 BRBRBWRBRBWRWRBWRBR。
• 以 W 分段：BRBRB，RBRB，R，RB，RBR。
• 对每一段按照 B 的个数分组，设 B 的个数为 $x$，将其分到第 $x+1$ 组：
  1. R。
  2. (B)，(BR)，RB，RBR（() 内的是不在这个例子中的情况）。
  3. (BRB)，(BRBR)，RBRB，(RBRBR)。
  4. BRBRB，(BRBRBR)，(RBRBRB)，(RBRBRBR)。
  5. …。
• 注意到每一组实际上是等价的。对于第 $i$ 组，只要染色操作序列存在对应的子序列，就可以得到这一组内所有的小球颜色序列：
  1. r。
  2. rb。
  3. rb?（? 是通配符）。
  4. rb??。
  5. …
• 因此，如果染色操作序列存在互不相交的五个子序列 rb??，rb?，r，rb，rb，则意味着合法，否则不合法。
• 按照要求的子序列长度从大到小贪心的匹配，先匹配 r，再匹配 b，再匹配 ? 即可。

可以发现我们枚举最终的小球颜色序列，会有非常多等价的情况。

由于每一段是相互独立的，因此我们把一个小球颜色序列无序地写成一个序列，表示每一段所在组的编号（例子中的 BRBRBWRRBRBBWWRRRRWRBBWWRRBBBR 写成的序列为 $1,2,2,3,4$），则写成的序列相同的是等价的。

这个序列类似整数拆分，所以其实可能的序列很少，在 $n = 70$ 的时候也只有 $418662$ 种。

最后的问题是，对于一个合法的序列，如何计算其对应了多少个最终的小球颜色序列呢？

依然以 $1,2,2,3,4$ 为例，首先是一个多重组合数 $\binom {5}{1,2,1,1}$，然后乘上一个方案数。

$1,2,2,3,4$ 这个序列对应的小球颜色序列一定包含子序列 RWBWBWBRBWBRBRB，长度为 $15$。而 unique 后一定是 WRWRBRWRBRWRBRBRWRBRBRBRW 的子序列，长度为 $25$。即相当于把 $n-15$ 个字符分成 $25$ 组，每组可以为空的方案数。考虑隔板法，答案为 $\binom {n-15+25-1}{25-1}$。

时间复杂度 $\mathcal O(能过)$。

代码

int n, k;
string s;
modint ans;

inline bool pd(vi p) {
    vector<bool> v(k, 0);
    vi t(p.size(), -1);
    for (ui i = 0; i < p.size(); i++) {
        while (++t[i] < k && (v[t[i]] || s[t[i]] == 'b'));
        if (t[i] == k) return 0;
        v[t[i]] = 1;
    }
    while (p.size() && p.back() == 1) p.pop_back();
    for (ui i = 0; i < p.size(); i++) {
        while (++t[i] < k && (v[t[i]] || s[t[i]] == 'r'));
        if (t[i] == k) return 0;
        v[t[i]] = 1;
    }
    while (p.size() && p.back() == 2) p.pop_back();
    for (ui i = 0; i < p.size(); i++)
        for (int j = 2; j < p[i]; j++) {
            while (++t[i] < k && v[t[i]]);
            if (t[i] == k) return 0;
            v[t[i]] = 1;
        }
    return 1;
}

void dfs(int o, int l, int r, vi p) {
    if (!o) {
        if (!pd(p)) return;
        modint now = binom(n - l + r - 1, r - 1);
        while (p.size()) {
            int t = 0, x = p.back();
            while (p.size() && p.back() == x) ++t, p.pop_back();
            now *= binom(p.size() + t, t); 
        }
        return ans += now, void();
    }
    while (1) {
        dfs(o - 1, l, r, p);
        l += (o == 1 ? 1 : 2 * o - 3) + (l != 0);
        if (l > n) return;
        r += 2 * o;
        p.pb(o);
    }
}

int main() {
    rd(n, k), rds(s);
    init(1e6);
    vi p;
    dfs((n + 3) >> 1, 0, 1, p);
    print(ans);
    return 0;
}