菜王的 blog

夜もすがら君想ふ - 西沢さんP / GUMI

首先我们对操作进行转化。这个操作可以变为，每一步可以将一个空位向左 / 向右移动两格，且不越过其他空位，也不与其他空位合并。这样的话我们的目标就是尽可能地操作空位使得它们不在 $S$ 中出现。注意操作显然是可逆的。

考虑对于一个棋盘和一个集合 $S$，如何判断 $S$ 是否合法。有一个这样的贪心：

• 首先将所有的空位尽可能的向左移动，直到无法操作。显然这样到达的最终局面是确定的。
• 若存在在 $S$ 中出现的空位，找到最靠左的那个，将它和它后面的空位都往右移动两格。持续进行此操作直到找不到这样的空位为止。
• 若在上一步中出现了把空位移出棋盘的情况则 $S$ 不合法，否则合法。

考虑根据这个贪心对 $S$ 计数。令 $k$ 为空位个数，尽可能向左移动后的最靠右的空位的位置为 $p$，那么我们向右移动的次数不能超过 $\lfloor\frac{n - p}2\rfloor$。枚举这个次数为 $i$，然后将移动分配到每个空位上，这样会导致 $S$ 中与空位产生冲突的位置被固定为 $1$，每个空位的最终位置被固定为 $0$，剩下的位置没有限制。那么可以写出式子：

$\sum_{i = 0}^{(n - p) / 2} 2^{n - k - i} \binom{k + i - 1}{k - 1}$

这样可以获得 $60$ 分。一次修改对 $p, k$ 的影响是 $\mathcal{O}(1)$ 的，考虑支持快速将 $p, k$ 加减 $1$。

$F(m, k) = \sum_{i = 0}^m 2^{n - k - i} \binom{k + i - 1}{k - 1}\\ \begin{aligned} F(m + 1, k) &= F(m, k) + 2^{n - k - m - 1} \binom{k + m}{k - 1}\\ F(m, k + 1) &= \sum_{i = 0}^m 2^{n - k - i - 1} \binom{k + i}{k}\\ &= \sum_{i = 0}^m 2^{n - k - i - 1} \left(\binom{k + i - 1}{k - 1} + \binom{k + i - 1}k\right)\\ &= \frac 12 F(m, k) + \sum_{i = 1}^m 2^{n - k - i - 1} \binom{k + i - 1}k\\ &= \frac 12 F(m, k) + \sum_{i = 0}^{m - 1} 2^{n - k - i - 2} \binom{k + i}k\\ &= \frac 12 F(m, k) + \frac 12 F(m - 1, k + 1)\\ &= \frac 12 F(m, k) + \frac 12 F(m, k + 1) - 2^{n - k - m - 2} \binom{k + m}k\\ F(m, k + 1) &= F(m, k) - 2^{n - k - m - 1} \binom{k + m}k\\ \end{aligned}$

$F(m - 1, k)$ 以及 $F(m, k - 1)$ 只需要解方程即可，$p, k$ 都可以简单地维护。那么本题时间复杂度为 $\mathcal{O}(n + q \log n)$，可以通过。

Bonus：这里有结论可以推导出：

$F(m, k) = 2^{n - m - k} \sum_{i = 0}^m \binom{m + k}i\\$

于是该问题和组合数下标求和是等价的。如果将全局询问改为区间询问，那么可以使用莫队来做到 $\mathcal{O}(q\sqrt n)$，或者使用多项式科技做到两只 $\log$ 的时间复杂度。