CF2027E1 Bit Game (Easy Version)

· · 题解

很有难度的 \operatorname{SG} 函数题。

显然这是取石子游戏的变种，只要能够快速求出每堆石子的 \operatorname{SG} 值，问题就得以解决。

首先定义 \operatorname{SG}(a,x) 表示限制为 a 当前有 x 个石子的状态对应的 \operatorname{SG} 值。如果你跟我一样，尝试写一个朴素的暴力去寻找规律，那么多半就死了。

这条路行不通的原因在于这个 \operatorname{SG} 函数中有两个变量，非常难以发现其中的规律。于是一个非常大胆的想法是，能否将这个 \operatorname{SG} 函数压成一个只有一个变量的函数呢？答案是可以的。

考虑对 (a,x) 进行一些调整。注意到这个拿石子操作本质上是拿走 x 二进制上的一些 1，那么将 (a,x) 放在二进制上进行观察。首先有如下几个比较简单的调整：

上面两个调整比较简单，不足以将 \operatorname{SG} 函数压维。

考虑从高到底找到最大的 i 满足 a 的第 i 位为 1，x 的第 i 位为 0，注意这一位本身就没有可以取的 1，那么相当于对于 0\sim i-1 位，这些位是可以任取的，于是可以将该位删除并把 a 的第 0\sim i-1 全部变为 1。最后一步调整是如果 p 满足 p\in [0,i-1] 且 x 的第 p 位是 0，那么第 p 位可以一并删掉。

设调整后的 a,x 分别为 a_2,x_2，一个非常好的性质是，x_2=2^k-1，其中 k 是最小的满足 2^k-1\ge a_2 的整数，也就是说调整后 x_2 二进制下一段前缀是 1，其余都是 0。

显然调整并不会对 \operatorname{SG} 的值造成影响，那么现在需要计算 \operatorname{SG}(a_2,x_2)，由于 a_2 决定了 x_2 的值，将其记作 g(a_2)。

一维就好找规律多了，这里直接给出规律：

前三个比较好证明，在纸上画一画发现就是普通的取石子游戏。重点是第 4 个性质，这个比较难证，首先要证明的是 k+1 取不到，这个很好证，因为每取一次新的 a_2 至少变为原来的 \frac{1}{2}，前面只有一个 g(2^k) 可能取到 k+1，主要是证 0\sim k 都出现了比较难，建议去看官方题解，不太容易说的清楚。

那么这个题就做完了，复杂度 \mathcal{O}(n\log V)。

代码：https://www.luogu.com.cn/paste/8f1ibti1