\(Nim\)游戏:
\(N\)堆石子，每堆\(a[i]\)个石子，\(Alice\)与\(Bob\)轮流行动，\(Alice\)先行动，操作规则如下 1、两方轮流操作 2、每次可取走任意一堆的任意数量石子，不能取成负数 3、无法行动的一方为输定义先手必胜局面，N局面，表示当前局面为先手必胜(即面对该局面的玩家一定有获胜的策略)
定义先手必败局面，P局面，表示当前局面为先手必败(即面对该局面的玩家一定没有机会获胜) 易得到\({\color{Red} {1、所有终止局面一定为P局面}}\)\({\color{Red} {2、可以到达P局面的局面为N面}}\)\({\color{Red} {3、所有操作都将导致N局面的局面为P局面}}\) 所以，博弈论的胜负决策可以按一下步骤确定 1、标记所有终止状态为P状态 2、寻找所有能到达P状态的点，标记为N状态 3、寻找所有子状态都为N状态的点，标为P状态。如果没有，则退出 但是，显然按上面这种算法会狂T不止，且码量巨大，所以，我们引进一个新函数 定义\(mex(x)\)，\(x\)为自变量，表示一个集合，\(mex(x)\)定义为集合中未出现过的最小自然数 定义\(sg(x)\)，令\(y\)为\(x\)的子状态集合，\(z\)为的某一元素\(y\)，则\(sg(x)=mex(sg(z))\) 又可以得到\({\color{Red} {sg(所有终止局面)=0(没有子状态)}}\)\({\color{Red} {sg(可达终止局面的状态)\ne0}}\)\({\color{Red} {sg(子状态的sg值均不为0的状态)=0}}\) 上面三个式子都很显然 然后，我们就发现了一个类似的规则 当\(sg=0\)时其状态为P状态 当\(sg\ne0\)时其状态为N状态(对比红字)如何判断多堆石子时的胜负情况？
首先，很显然， 当局面为 \(\begin{matrix}2n\\\overbrace{ k+k+\cdots+k }\end{matrix}\) 时，先手必输 设\(N\)堆石子，每堆数量为\(a_{i}\) 将每个\(a_{i}\)转化为二进值，并将前导零补全 当\(a_{i}=a_{j}=k(1\leq i<j\leq n)\)时 所有\(a_{i}\)转化为二进值都是相同的 例如，\(k=22\)时\(10110\)\(10110\) 每次先手的操作，都可以看做在其中一个\(k\)中，将一些0变为1,1变为0 例如把k取成17\(10{\color{Red} {001}}\)\(10110\) 此时对手也可以采取相同操作，将下面的也取成17\(10{\color{Red} {001}}\)\(10{\color{Red} {001}}\) 上面一点大家都懂，只是一个引入当存在\(a_{i}\ne a_{j}\)时，如何操作？
拿3、5、6为例\(011\)\(101\)\(110\) 观察发现，每一纵列都有偶数个1，这意味着当一方取走任意一个1时，另一方都有相同的策略取走另一个1，使其保持纵列仍然为偶数个1当一方将任意一个0改变为1时，另一方都有相同的策略取走一个1(注意，不是补0)，使其保持纵列仍然为偶数个1 这跟上面讲到过的策略一样，正确性显然 所以，我们得出这么一个结论，当每一列的1的个数均为偶数时，先手必败，反之先手必胜 再简化一点，当\(a_{1}\otimes a_{2}\otimes a_{3}\otimes\cdots\otimes a_{n}=0\)时(\(\otimes\)表示异或)，先手必败，反之先手必胜 再推广，可得一个平等组合游戏中，该游戏的\(sg\)值等于其所有子游戏的\(sg\)值的异或和胜负判断知道了，如何得到必胜策略(如果存在的话)
设\(a_{1}\otimes a_{2}\otimes a_{3}\otimes\cdots\otimes a_{n}=k(k\ne0)\) 因为\[a_{1}\otimes a_{2}\otimes a_{3}\otimes\cdots\otimes a_{n}=k(k\ne0)\] 很显然\[a_{1}\otimes a_{2}\otimes a_{3}\otimes\cdots\otimes a_{n}\otimes k=k\otimes k=0\] 且\[k\leq max(a_{1},a_{2},a_{3},\cdots,a_{n})\] 设k的二进值最高位为第x位，则在\(a_{1}\sim a_{n}\)中，至少存在一个\(a_{i}\)，二进值第x位也为1 所以\[a_{i}\otimes k<a_{i}\]\[a_{1}\otimes a_{2}\otimes a_{3}\otimes\cdots\otimes a_{i}\otimes k\otimes\cdots\otimes a_{n}=0(k\ne0)\] 因为\(a_{i}\otimes k<a_{i}\)，所以存在\(a_{i}\)，将其取成\(a_{i}\otimes k\)即可