首先我们对操作进行转化。这个操作可以变为，每一步可以将一个空位向左 / 向右移动两格，且不越过其他空位，也不与其他空位合并。这样的话我们的目标就是尽可能地操作空位使得它们不在 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}
Bonus：[这里](https://www.luogu.com.cn/article/6ovnnikq)有结论可以推导出：
$$
F(m, k) = 2^{n - m - k} \sum_{i = 0}^m \binom{m + k}i\\
$$
于是该问题和组合数下标求和是等价的。如果将全局询问改为区间询问，那么可以使用莫队来做到 $\mathcal{O}(q\sqrt n)$，或者使用多项式科技做到两只 $\log$ 的时间复杂度。