题目

点这里看题目。

分析

首先注意到黑白石子是独立的两个游戏，我们可以分别求出它们的 \(sg\) 值，然后异或起来得到整个游戏的 \(sg\) 值。

之后分开考虑，白石子就是 Nim，因此白石子的 \(sg\) 值就是每堆白石子的数量的异或。

接着考虑黑石子。注意到我们每次只能操作最少的一堆，那么将所有石子堆按照数量排序后，我们就相当于每次只能操作第一堆，如果操作完了就换下一堆。在有序的情况下，我们可以从后往前合并每一堆。因此如果有 \(k\) 堆黑石子，我们可以设排序后，第 \(i\) 堆有 \(b_i\) 颗石子，而 \([i,k]\) 的石子堆组成的局面的 \(sg\) 值为 \(f_i\)。

考虑从 \(f_{i+1}\) 转移到 \(f_i\)。类似于 Nim 的推导过程，我们可以设计出 \(g_j\) 为第 \(i\) 堆石子还剩 \(j\) 颗时局面的 \(sg\) 值。那么就有：

\[\begin{aligned} g_0&=f_{i+1}\\ g_j&=\operatorname{mex}\{g_l|0\le l<j\},j=1,2,\dots,b_i \end{aligned} \]

手玩一下可以找出规律：

\[f_i=g_{b_i}=b_i-[b_i\le f_{i+1}] \]

尝试使用这个规律计算任意一个位置的 \(f\)。如果 \(i<k,b_i<b_{i+1}\)，那么 \(f_i\) 一定为 \(b_i-1\)；否则就是 \(b_i=b_{i+1}\)，此时 \([b_i\le f_{i+1}]\) 取决于 \(i\) 在连续相同段中所处的位置和这一段相同的值在 \(b\) 中所处的位置，总结如下：

• 如果 \(b_i=\max_{1\le j\le k} b_j\)，那么 \(f_i=b_i-(k-i)\bmod 2\)；
• 否则，设在 \([i,k]\) 中有 \(s\) 堆石子数量与 \(b_i\) 相同，那么 \(f_i=b_i-[(s-i)\bmod 2=0]\)；

在原问题中我们只关心 \(f_1\)，而 \(f_1\) 仅仅取决于 \(b_1\) 和 \(b_1\) 所处的位置，所以我们可以从大到小枚举 \(b_1\)。枚举好 \(b_1\) 之后，假设在 \(a\) 中有 \(t\) 堆石子数量为 \(b_1\)，此时我们有 \(2^t\) 种方式选出 \(s\) 为奇数的情况，有 \(2^t-1\) 选出 \(s\) 为偶数的情况。下面是讨论：

• 如果我们令 \(b_1=\max_{1\le j\le k}b_j\)，那么这就意味着除了选出来的一些数量都为 \(b_1\) 的黑石子堆，其余都是白石子。我们可以分 \(s\) 为奇数和偶数，这样白石子的异或和是确定的，我们只需要检查此时黑白 \(sg\) 值的异或和是否为零，并计算贡献即可；

• 否则，这说明一定有数量超过 \(b_1\) 的石子堆被涂黑。此时黑石子的 \(sg\) 值和所有 \(\le b_1\) 的白石子的 \(sg\) 值可以被算出，不妨设已知的 \(sg\) 值为 \(v\)，我们相当于要从后面的石子堆中选出一个真子集（这个子集内的石子堆会被染白），使得子集中的石子异或出的值和 \(v\) 异或后得到 0。

  这其实就是计算方程解的数量的问题，在 \(\bmod 2\) 意义下计算解数是很容易的：我们只需要判断 \(v\) 能否被解得，那么解的数量就是 \(2^{\text{*元个数}}\)。而一个数是否为*元取决于它是否在基内，因此我们可以维护一个异或线性基，以此判断 \(v\) 能否被解出，同时非*元的数量就是基的大小。

  当然，我们还需要检查如果后面的石子堆全选了是否会得到 0，如果是，那么还需要减去这种情况的贡献。

我们因而可以得到 \(O(n\log_2(\max a))\) 的算法。

小结：

1. 注意推导 \(f\) 过程中，调整类似的推导来解决当前问题的方法！
2. 熟悉一下求 \(\bmod 2\) 意义下方程解的个数的方法。
3. 不要害怕分类讨论