【未知出处】 翻转颜色 解题笔记

· · 个人记录

【题目描述】

给定一个长度为 2n 的字符串 S，S 表示 2n 个格子的染色情况。S_i (1 ≤ i ≤ 2n)为 B 时表示第 i 个格子为黑色；否则 S_i 为 W，表示第 i 个格子为白色。

你需要进行恰好 n 次操作，使得所有格子的颜色都变为白色。第 i 次操作时，你可以选择两个未在之前操作中选择过的格子 l_i ,r_i (l_i < r_i )，并翻转所有下标在 [l_i ,r_i] 中的格子的颜色。所有操作结束后，每个格子应恰好被选择一次。

请求出合法操作序列的方案数对 10^9 + 7 取模的结果。我们认为两个操作序列不同，当且仅当存在某个正整数 i ∈ [1,n] 使得两个操作序列对应的 l_i 不同或 r_i 不同。

思路：

记：一对[l_i,r_i]为一个“变色区间”。

由于最终状态下所有格子均为白色，则初始位置为黑色的格子必定被奇数个“变色区间”所包含，反之则被偶数个“变色区间”所包含。

举个栗子：我们用"("表示一对“变色区间”的左端点，")"为右端点，则序列"BWBBWWWB"所对应的“变色区间”的状况可被表示为"((())())"。

完成以上转化后，解题思路已经明晰。由于一个序列与一组“变色区间”一一对应（即：一个序列对应的“变色区间”情况是唯一的），并且某一个左端点与任意右端点相匹配，均不影响最终结果。因此我们可以在构建好括号序列时从左往右扫描之，遇到右端点时统计答案。每个右端点对答案的贡献为：当前未被匹配的左端点个数。把每个右端点的贡献乘起来，最后再乘 n! 即可。

注：由于要进行n次操作将格子全部变为白色，则一个序列必定有恰好n个“变色区间”。而选择“变色区间”的先后顺序与结果也无关，且按照不同顺序选择n个“变色区间”的所有可能有n!种，因此最后答案需要乘 n! 。别忘了取模！