Luogu5387 [Cnoi2019] 人形演舞

题意：对一堆大小为 的石子，可以做以下操作 ：

• 选定 ，使得 ，并将石子数拿至 。

现在有 堆石子，每一堆的大小都在 中。

两人轮流操作，不能操作者负。问先手必胜的情况数。

答案对 取模，，。

---

首先推一下 函数。

首先显然有 。

注意到 的限制，考虑 的最高位，设

若 ，则 可任取。后继状态有 。

若 ，相当于求 的所有后继，只需考虑 。

考虑归纳证明 ： 对于 ，。

对于 的情况，后继状态只有 ，则 。

对于 的情况，后继状态有 以及 的后继。

则后继 有 ，由归纳结论显然有 。

所以 。

容易求出 的 值。

---

现在问题变为：在集合 中选择 次元素，使得异或和非 的方案数。

异或卷积快速幂即可。

复杂度 。