一个游戏满足：
由两名玩家交替行动
在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关
不能行动的玩家判负
则称该游戏为一个公平组合游戏。
尼姆游戏（NIM）属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较负责，不满足条件2和3。
题目描述
给定nn堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。
操作步骤：
- 先手从第二堆拿走1个，此时第一堆和第二堆数目相同
- 无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可。
必胜状态和必败状态
在解决这个问题之前，先来了解两个名词：
必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。
结论
假设nn堆石子，石子数目分别是a1,a2,…,ana1,a2,…,an，如果a1⊕a2⊕…⊕an≠0a1⊕a2⊕…⊕an≠0，先手必胜；否则先手必败。
证明
操作到最后时，每堆石子数都是00，0⊕0⊕…0=00⊕0⊕…0=0
在操作过程中，如果 a1⊕a2⊕…⊕an=x≠0a1⊕a2⊕…⊕an=x≠0。那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为0。
证明：不妨设x的二进制表示中最高一位1在第k位，那么在a1,a2,…,ana1,a2,…,an中，必然有一个数aiai，它的第k为时1，且ai⊕x<aiai⊕x<ai，那么从第ii堆石子中拿走(ai−ai⊕x(ai−ai⊕x)个石子，第ii堆石子还剩ai−(ai−ai⊕x)=ai⊕xai−(ai−ai⊕x)=ai⊕x，此时a1⊕a2⊕…⊕ai⊕x⊕…⊕an=x⊕x=0a1⊕a2⊕…⊕ai⊕x⊕…⊕an=x⊕x=0。
在操作过程中，如果 a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0，那么无论玩家怎么拿，必然会导致最终异或结果不为00。
反证法：假设玩家从第ii堆石子拿走若干个，结果仍是00。不妨设还剩下a′a′个，因为不能不拿，所以0≤a′<ai0≤a′<ai，且a1⊕a2⊕…⊕a′⊕…⊕an=0a1⊕a2⊕…⊕a′⊕…⊕an=0。那么(a1⊕a2⊕…⊕ai⊕…an)⊕(a1⊕a2⊕…⊕a′⊕…⊕an)=ai⊕a′=0(a1⊕a2⊕…⊕ai⊕…an)⊕(a1⊕a2⊕…⊕a′⊕…⊕an)=ai⊕a′=0，则 ai=a′ai=a′，与假设0≤a′<ai0≤a′<ai矛盾。
基于上述三个证明：
- 如果先手面对的局面是a1⊕a2⊕…⊕an≠0a1⊕a2⊕…⊕an≠0，那么先手总可以通过拿走某一堆若干个石子，将局面变成a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0。如此重复，最后一定是后手面临最终没有石子可拿的状态。先手必胜。
- 如果先手面对的局面是a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0，那么无论先手怎么拿，都会将局面变成a1⊕a2⊕…⊕an≠0a1⊕a2⊕…⊕an≠0，那么后手总可以通过拿走某一堆若干个石子，将局面变成a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0。如此重复，最后一定是先手面临最终没有石子可拿的状态。先手必败。
c++代码
#include #include using namespace std; /* 先手必胜状态：先手操作完，可以走到某一个必败状态 先手必败状态：先手操作完，走不到任何一个必败状态 先手必败状态：a1 ^ a2 ^ a3 ^ … ^an = 0 先手必胜状态：a1 ^ a2 ^ a3 ^ … ^an ≠ 0 */ int main(){ int n; scanf(“%d”, &n); int res = 0; for(int i = 0; i < n; i++) { int x; scanf(“%d”, &x); res ^= x; } if(res == 0) puts(“No”); else puts(“Yes”); }
