ablog

#算法 #icg #nimm游戏

$n$ 堆物品，每堆有 $a_{i}$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。取走最后一个物品的人获胜

定义 必胜状态 为 先手必胜的状态，必败状态 为 先手必败的状态。

结论

$a_{1} \oplus a_{2} \oplus a_{3} . . . \oplus a_{n} \neq 0$ 当前状态获胜，反之，当前状态失败

通过推理，我们可以得出下面三条定理：

为什么异或值会和状态的胜负有关？下面给出了这个定理的证明过程。

为了证明该定理，只需要证明下面三个定理：

·定理 1: 没有后继状态的状态是必败状态。

·定理 2: 对于 $a_{1} \oplus a_{2} \oplus \dots \oplus a_{n} \neq 0$ 的局面，一定存在某种移动使得 $a_{1} \oplus a_{2} \oplus \dots \oplus a_{n} = 0$ 。

==·定理 3: 对于 $a_{1} \oplus a_{2} \oplus \dots \oplus a_{n} = 0$ 的局面，一定不存在某种移动使得 $a_{1} \oplus a_{2} \oplus \dots \oplus a_{n} = 0$ ==

对于定理 1, 没有后继状态的状态只有一个，即全 0 局面。此时 $a_{1} \oplus a_{2} \oplus \dots \oplus a_{n} = 0$ 。

对于定理 2,不妨假设 $a_{1} \oplus a_{2} \oplus \dots a_{n} = k \neq 0$ 。如果我们要将 $a_{i}$ 改为 $a_{i}^{'}$ ,则 $a_{i}^{'} = a_{i} \oplus k$ 。

假设 $k$ 的二进制最高位 1 为 $d$ ,即 $2^{d} \leq k < 2^{d + 1}$ 。根据异或定义，一定有奇数个 $a_{i}$ 的二进制第 $d$

位为 1。满足这个条件的 $a_{i}$ 一定也满足 $a_{i} > a_{i} \oplus k$ ,因而这也是个合法的移动。

对于定理 3,如果我们要将 $a_{i}$ 改为 $a_{i}^{'}$ 则根据异或运算律可以得出 $a_{i} = a_{i}^{'}$ 因而这不是个合法的

移动。

对于 $a_{1} \oplus a_{2} \oplus \dots \oplus a_{n} = 0$ 的局面,对于第 $i$ 位 ,都是偶数个1, 无论减多少都会令其中一位或多位 $i$ 的1的数量由偶数变为奇数 ,最终让第 $i$ 位不为0