ARC089F ColoringBalls 题解

作者: xht37 分类: 题解 发布时间: 2020-04-27 19:35

点击数:95

ARC089F ColoringBalls

题意

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

题解

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

考虑如何判断,以 BRBRBWRRBRBBWWRRRRWRBBWWRRBBBR 为例:

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注