Nim游戏：取石头

（一）一堆取石头

背景：

在博弈论中，有一种称为Nim游戏的经典问题，它涉及到取石子的问题，其中有许多变种。Nim游戏是一种零和博弈，即两名玩家交替行动，每次只能从一堆物品中取走一定数量的物品，无法分割物品。

题目中描述的场景是这样的：

有n个石头，两名玩家轮流进行操作，每次可以从石头堆中取走1到m个石头（其中m是一个固定的正整数）。玩家可以根据自己的策略选择取多少个石头，目标是使自己取得最后一个石头。

题解思路：

令 ans = n%（m+1）（为什么这样令，后面会讲解）

判断是否存在先手必胜策略这一问题，即可一开始检验石子堆中的ans是否为0，当ans为0时，你面对的是ans==0的局面，你的任意操作都会使得当前ans不为0，你的对手又足够聪明，那你每执行一步，他都会再次把ans==0的局面返还给你，那你最后必输；

当ans不为0时，你先手，你又足够聪明，你每次执行后都可以把ans==0的局面留给对手，最后你必胜。

• 为什么令 ans = n%（m+1）？

当先手玩家取石头使石头个数 n 能够被（m+1）整除时，后手玩家所要面临的情况是：无论怎么取都不可能取完石头。如果先手玩家能够保证后手玩家一直面临石头个数 n 能够被（m+1）整除，那么最后一次，后手玩家面临的情况是：石头的个数是 m+1，所以后手玩家无论怎么取都不可能取完石头，最后只能是先手玩家将石头取完。

所以对于自己来说，取胜的条件是：自己面临的石头个数情况是 n%（m+1）!= 0；然后自己取石头使石头个数能够被（m+1）整数。

（二）多堆取石头：

这里我转载一位大佬的博客：博弈论石子游戏——nim 游戏_[模板]nim游戏_Wu_L7的博客-CSDN博客

题目描述：

地上有 n 堆石子（每堆石子数量小于 10^4），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 n 堆石子的数量，他想知道是否存在先手必胜的策略。

题目思路：

必胜策略，即当你执行最后一步后，你的对手已无石子可取，他必败你必胜。最后局面是地上各个石子堆已无石子可取，假设 ai 代表第 i 个石子堆中的石子数，则 ai = 0（i ≤ n）。即可得，a1^a2^a3^……^an=0（^表示异或），令ans = a1^a2^a3^……^an，要想必胜，说明最后的局面一定是ans==0，那我只需要满足，我每次操作完使得ans==0即可，那么每次留给对手的局面都是ans==0（怎么实现后面讲），并且石子的初始数确定，每次都取走一部分的石子，在有限的步数内肯定会取完，当执行到最后一步ans==0时，恰好最后的石子被你取完，你必胜。

那么，判断是否存在先手必胜策略这一问题，即可一开始检验石子堆中的ans是否为0，当ans为0时，你面对的是ans==0的局面，你的任意操作都会使得当前ans不为0，你的对手又足够聪明，那你每执行一步，他都会再次把ans==0的局面返还给你，那你最后必输；当ans不为0时，你先手，你又足够聪明，你每次执行后都可以把ans==0的局面留给对手，最后你必胜。

小tip：

为什么每次操作之后都会使得ans==0转化成ans != 0，并且足够聪明的你执行完一次操作之后又能把ans != 0变成ans==0？

1、ans==0执行一次操作之后为什么会转化为ans != 0？

异或，即是把每个ai中转化为二进制的形式，再对每一个位置的所有0和1进行异或操作，举个例子：5^3=6（0101^0011=0110）。而ans = a1^a2^a3^……^an，每次只能对一个石子堆操作，即每次操作只会影响ai（i ≤ n）中的一个，假设是对ak进行操作，则（没操作前的ak）^（其它ai的异或）==0，说明（其它ai的异或）==（没操作前的ak）（因为两个相同的数相异或结果才为0），现在对ak进行操作，则ak的值肯定会变化，其二进制形式也随之变化，则（操作后的ak）!=（其它ai的异或），所以（操作后的ak）^（其它ai的异或）!= 0，则ans != 0。

2、为什么足够聪明的你执行完一次操作之后又能把ans != 0变成ans==0？

ans = a1^a2^a3^……^an，是各个位置多个0和1的异或，因为ans != 0，说明一定有个别位置中1的个数为奇数，则我们可以把该位置上的1去掉一个或增加一个，即取走一些石头，使之为偶数，则ans==0。例如：10^5=15（1010^0101=1111），这是最经典的了，我们可以从10中拿走5，则5^5=0，所以想说明的是，总有办法使ans==0。
 

注：

这里有个简单的取石头个数的技巧（异或的简单计算方法）：

例如：7和14的异或

7的二进制序列为：  0111

14的二进制序列为：1110

则异或结果是：1001 == 9

简便计算：

7可以写成2的倍数之和：4+2+1

14可以写成2的倍数之和：8+4+2+0

然后约去两部分相同的部分：7剩余一个1；14剩余一个8，再将剩余的数相加，其结果就是异或结果9。

---

本次内容到此结束了！如果你觉得这篇博客对你有帮助的话 ，希望你能够给我点个赞，鼓励一下我。感谢感谢……

参考资料：

【尼姆游戏（学霸就是这样欺负人的）】https://www.bilibili.com/video/BV1ek4y1q7JD?vd_source=564abed1c36a31978eb9de7cdc6668d2

博客原文链接：https://blog.csdn.net/Wu_L7/article/details/126266519

同时感谢上面两位创作者的输出，让我受益匪浅。