nim游戏 题解

给定一个石子堆序列，你可以向第 $i$ 个石子堆添加 $x_i$ 个石子使得 $\oplus_{i=1}^n(a_i+x_i)=0$，求出 $\sum x$ 的最小值，并求出至多 $m$ 种好的方案。

第一问的分数占 $50\%$。

$n\le10^5,m\le 2\times 10^4,a_i<2^{60}$。

• 每位可以分配偶数个 $1$，需要保证分配到每个数上的和 $\ge a_i$。
• 从高往低更改，扫到第 $i$ 位的时候选择一些此刻该位为 $0$ 的数，将该位置 $1$，并把它们的低位置 $0$。

我们来证明这个结论。

假设我们在第 $i$ 位更改了 $\ge 2$ 个数，随便挑选其中的两个数，令它们的低位是 $x,y$，则代价是 $2^i-x+2^i-y$，对总异或和的影响是 $x\oplus y$。

考虑低位的合法方案，我们可以花费至多 $x\oplus y$ 的代价（在 $a_1$ 上）构造一个新的合法方案。

这个方案和原方案的代价差小于 $x\oplus y-(2^i-x+2^i-y)$，显然 $x\oplus y+x+y<2^{i+1}$（$x,y,x\oplus y$ 三个数中每位至多两个 $1$）。

所以我们证明了原方案不优。

并且新方案的低位多了 $x,y$ 可以选择，若选择它们还可以减少代价。

这个好证，假设我们有两个选项其低位是 $x,y,x>y$，假设我们选了 $y$，贡献是 $2^i-y$，若后面 $x$ 都没有被选，则显然换成 $x$ 更优。

若之后 $x$ 又被选了，找出 $x$ 被选的最高位 $j$，若 $j\ge$ $x,y$ 的 $\rm lcp$，显然 $x,y$ 选哪个是一样优的，若 $j<\text{lcp}$，则 $y+(x\bmod 2^j)\le x$，这意味着我们直接高位选 $x$，然后在 $x$ 空出来的第 $j$ 位上选一个都不劣。