ARC089F ColoringBalls 题解

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;
}

题意

题解

代码

评论