「AtCoder」「JSC 2019 Qual C」Cell Inversion
题意
有 \(2n\) 个格子，每个格子初始为黑色或白色。你需要执行恰好 \(n\) 次操作，使得最后所有格子变成白色。每次操作你可以选择两个从未选择过的格子 \(l,r (l < r)\)，然后将区间 \([l,r]\) 的所有格子的颜色取反，即黑色的格子变成白色，白色的格子变成黑色。求方案数 \(\bmod 10^9+7\) 的值。
两个方案不同当且仅当存在一个 \(i\in [1,n]\)，满足第 \(i\) 次操作选择的两个格子至少有一个不同。
\(n\le 10^5\)
题解
我们发现，操作的顺序与最后结果无关，于是我们强制 \(l\) 从小到大，最后乘上 \(m!\) 即可。
从左往右对于每个格子 \(i\)，设 \(m\) 次操作中有 \(x\) 个操作 \(l < r < i\)，有 \(y\) 个操作 \(l < i\le r\)，那么有 \(y=i-1-2x\)，所以 \(y\) 与 \(i-1\) 的奇偶性相同，于是可以直接判断 \(y\) 的奇偶性。若 \(y\) 是偶数，那么执行完所有 \(l < i\) 的操作后，\(i\) 的颜色不会变化，此时若 \(i\) 是黑色，那么一定存在一个操作 \(l = i < r\)，否则一定不存在，即一定存在一个操作 \(l < i = r\)。\(y\) 为偶数同理。
经过上述处理，我们已经知道了每个格子是作为 \(l\) 被选择还是作为 \(r\) 被选择。
我们又发现，两个操作 \(l_1,r_1\) 和 \(l_2,r_2\)（\(l_1 < r_2,l_2 < r_1\)），变成 \(l_1,r_2\) 和 \(l_2,r_1\) 结果也是不变的。
那么我们只要把所有左端点和右端点任意匹配即可。对于每个作为右端点的 \(i\)，记 \([1,i-1]\) 中作为左端点的点的数量减去作为右端点的点的数量为 \(d\)，即多余的左端点个数，那么 \(i\) 可以与这 \(d\) 个左端点中的任意一个进行匹配，答案乘上 \(d\)。最后再乘上 \(m!\) 即可。
时间复杂度 \(O(n)\)。
代码
1 |
|
