PART1. 经典nim

出处

问题：

有n堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)，没法拿的人失败。问谁会胜利

算法：

若每堆石子数的异或和不为0，则先手必胜

证明：

由于nim游戏的sg值与石子数相等，所以由SG定理可以方便的得到

例题：

P2197 【模板】nim游戏

PART2. 分裂nim

出处

新规则：

每次取完石子后，可以将取的那一堆的石子 分为多堆，也可以不分

算法：

与经典无异

证明：

如果异或和不为0，那先手不用分某一堆石子，同Nim游戏

如果异或和为0，

不执行分裂操作则先手必败，同Nim游戏

若执行分裂操作，如果能够证明执行分裂操作的后继局面异或和依然不为0，那么结论成立

采用反证法，证明如果分裂后异或和为0 会产生矛盾

a1 xor a2 xor a3 xor ……xor an=0

a1=a2 xor a3 xor ……xor an

假设我们取的那一堆是第1堆，取完之后还有b1个，b1<a1

将b1分为x+y

若x xor y xor a2 xor a3 xor ……xor an=0

则 x xor y=a2 xor a3 xor …… xor an

所以x xor y = a1

又因为异或是不进位的加法，所以x xor y<=b1<a1产生矛盾

PART3. 阶梯nim

出处

新规则：

取的石子不是拿出而是从第i堆放入第i-1堆

算法：

将每个奇数位置的数x看成一堆有x个石子的石子堆，然后玩Nim游戏。

证明：

　　拿走某一堆石子的一部分，相当于将某个奇位置的石子移动到它左边的偶位置上。
　　
　　如果大家都只动奇位置的石子，那么这等价于两人在玩Nim游戏。
　　
　　但如果有人想打破规则呢？
　　
　　假设Nim游戏先手必胜，那么先手肯定优先玩Nim游戏；如果后手试图破坏局面，将某个偶位置上的若干石子移动到了左边的奇位置i上，那么先手可以将这若干个刚移到i的石子继续移动到i左边的偶位置上，对Nim局面依然没有任何影响，除非后手回头来继续动奇位置的石子，那也只能是输。
　　
　　那么如果Nim游戏先手必败，也是同理，后手可以用相同的方式迫使先手玩Nim游戏，直到输为止。
　　
　　因此，奇数位置的石子的相关信息，就直接决定了阶梯Nim问题的结果。 　　

例题：

POJ1704 Georgia and Bob

PART4. 树上阶梯nim

新规则：

在阶梯nim的基础上赋予各节点树的顺序

算法：

对深度为奇数的所有点玩Nim游戏。

证明：

　　根据SG定理，在阶梯nim的基础上做异或合并即可 　　

例题：

这个文档的T3

赏

OIer