Nim博弈
甲，乙两个人玩 nim 取石子游戏。
nim 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
分析：
- 如果只有一堆石子，第一个人拿走所有石子，一定会赢。
- 如果有两堆相同的石子，第一个人拿多少石子，第二个人就在另一堆拿一样个数的石子，最后第一个人一定会输。
- 考虑将石子数表示为状态 \((a_1,a_2,a_3,...)\)。考虑如果知道 \(s=(a_1,a_2,...,a_m)\) 和 \(t=(b_1,b_2,...,b_n)\) 的胜负性（先手是不是必胜），那么可以叠加地求出 \(s+t=(a_1,a_2,...,a_m,b_1,b_2,...,b_m)\) 的胜负性。
如果 \(s\) 和 \(t\) 都为负，那么先拿的人拿走一堆中的某些石子之后，后拿的人可以按照必胜策略拿同一堆石子。如果这一整堆石子拿完了，那么另外一堆也一样。如果先拿的这个人率先取了另一堆的石子，后拿的人也可以按照相应必胜策略应对。总之，最后是先拿的人输，即 \(s+t\) 负。
如果 \(s\) 和 \(t\) 有一个为胜一个为负，那么先拿的人在胜的那一堆里按照必胜策略拿取一些石子，局面变为负+负，此时一开始后拿的人拿了，必负。故先拿的人赢，即 \(s+t\) 胜。
如果 \(s\) 和 \(t\) 都为胜，那么不确定。 - \((x_1,x_1,x_2,...)\) 的胜负性等于 \((x_2,...)\) 的胜负性，因为相当于拆成 \((x_1,x_1)\) 负和 \((x_2,...)\)，这个东西的正负性由 \(3\) 知道就是 \((x_2,...)\) 的正负性。
这样的好处是，我们可以将一个状态变成里面的元素都不一样的。 - 考虑 \(\#s\) 为 \(s\) 状态中所有数的异或和。那么我们有如下状态合并法则：
- \(a==b\)，那么 \(\#s=0\)。
- \(a==(k),b==0\)，那么 \(\#s=k\)。
- \(a==0,b==(k)\)，那么 \(\#s=k\)。
- \(a==0,b==0\)，那么 \(\#s=0\)。
发现这个东西非常像刚刚的状态胜负性合并法则。具体地说，如果 \(a\) 和 \(b\) 满足如上条件，那么 \(\#s\) 为 \(0\) 的话胜负性为负，否则为正。
- 证明这个东西，即 \(\#s\) 等于正负性。
如果 \(\#s \ge 0\)，假设其最高位为 \(i\)，取 \(s\) 中一个第 \(i\) 位是 \(1\) 的数，将其记为 \(a\)，其他数记为 \(t\)。那么 \(\#s=\#a ⊕ \#t\)。让第一个人取 \(s\) 这一堆里面的石子，使剩下的个数为 \(\#a ⊕ \#s < \#s\)，那么剩下的东西的 \(\#\) 是 \(\#a ⊕ \#s ⊕ \#t = 0\)。那么如果有 \(\#s>0\)，那么一定有一种取法 \(s->t\) 使得 \(\#t==0\)。
易证，如果有 \(\#s=0\)，那么无论哪一种取法 \(s->t\) 都使得 \(\#t>0\)。
因为个数一直减小，所以最后得到一堆 \(\#k=0\) 时，先手胜。
综上所述，\(\#s>0\) 的时候，先手必胜。\(\#s==0\) 的时候，后手必胜。
结论：
如果这些石子的数量异或和为 \(0\)，后手必胜；否则先手必胜。
推广：
- 如果每次只能取不超过 \(m\) 个：
若所有石子模 \(m\) 的异或和不为 \(0\)，则先手胜，反之则后手胜。 - 通法：\(SG\) 函数
我们用一个 \(n\) 元组 \((a_1,a_2,...,a_n)\) 描述过程中的一个场面。
用 \(\#s\)，表示局面 \(s\) 对应的二进制数。
如果局面 \(s\) 只有一堆石子，那么用这一堆石子数目所对应的二进制数来表示 \(\#S\)。
设局面 \(S=(a_1, a_2, …, a_n)\)，\(\#S=\#a_1?+\#a_2+…+\#a_n\)，采用异或操作。
但是这里的 \(\#a_i\) 并不是一直都等于本身的二进制数的，而是应该换作一个函数，这个函数，根据题目的不同而有所不同。
这，就是 \(SG\) 函数
通常解法： 首先，把原局面分解成多个独立的子局面，则原游戏的 \(SG\) 函数值是它的所有子局面的 \(SG\) 函数值的异或和。
即 \(SG(S)=SG(s_1) ⊕ SG(s_2) ⊕ ... ⊕ SG(s_n)\)。
然后，分别考虑每一个子局面，计算其 \(SG\) 值。
后手必胜当且仅当 \(SG\) 的异或和为 \(0\)。