我发现网上好多博客写的都是错的。。。
甚至有些人没搞明白就写 真是绝了
Nim游戏
Nim 游戏的定义如下：
假设当前有 $n$ 堆石子，第 $i$ 堆有 $x_i$ 个，两个人轮流操作，每次操作可以选择一堆，然后移除任意多个石子（不能移除 $0$ 个）。
不能操作的人失败，问是否先手必胜。
然后这个游戏有一个很简单的解法，先给出答案：
如果 $x_1\oplus x_2\oplus \cdots \oplus x_n=0$ ，则先手必败，否则先手必胜（其中 $\oplus$ 表示异或）。
证明考虑使用数学归纳法：
首先结束状态异或和为 $0$ 。
然后分情况讨论：
- 如果当前异或和为 $0$ ，那么你的一次移动必然会改变异或和，到达一个必胜状态，所以当前必败。
- 否则，假设异或和为 $t$ ，找到 $t$ 的二进制最高位 $a$ ，然后我们找到一个 $x_i$ ，满足他第 $a$ 位是 $1$ （必然能找到，不然异或和这一位为 $0$ ），然后把他改成 $x\oplus t$ 即可（肯定是会减小的），那么此时到达了一个必败状态。
任意公平博弈游戏与 Nim 游戏的转化
可以添加石子的 Nim
我们给 Nim 游戏加两条规则：
- 不能循环。
- 每次操作可以给一堆增加若干石子。
可以用归纳法简单证明，新添的两条规则没有意义，也就是说不会用到添加石子这个条件。
- 如果当前必胜，那显然不会用到。
- 否则，如果你给某一堆加了一些石子，另一个人立刻拿掉这些即可。因为不能循环，所以你最终还是要拿掉某些石子。
SG函数
对于一个双人公平博弈游戏，首先我们把一个状态看成一个点，如果一个状态可以到另一个状态，我们就连一条有向边。
如果这个图有环，要么有些环边用不上，要么游戏陷入循环。
我们给这个游戏加一条规则：不能循环（这条规则基本上是默认的）。
那么我们可以得到一个无环的图。
对于一个点，我们定义一个函数 $sg(x)$ ，并有如下转移式：
其中 $v_i$ 表示 $x$ 指向的所有点， $\rm mex$ 函数 (minimum exludant) 表示不在当前集合内的最大非负整数。
举个例子：$\rm mex\{0,1,3\}=2,mex\{1\}=0$。
注意到根据 sg 函数的性质可以发现，sg 函数的值不超过 $\sqrt n$ 。
转化为 Nim
其实就是说，假设当前起始状态为 $x$ ，那么可以看作是一个 $n=1,a_1=sg(x)$ 的 Nim 游戏。
显然你每次可以任意减小 sg 值，或者增大特定的值，但是先前讨论过了增大是无意义的，所以这两者等价。
这东西有啥用
首先可以发现，对于一个游戏，如果 $sg(x)=0$ 则当前状态必败，否则必胜。
但是这个显然是没用的。。。只需要记录 $0/1$ 可以做到一样的事情。
这玩意 nb 的地方就在于，如果你现在有多个毫不相关的游戏，你每次可以操作某个游戏一次，如果不能操作就输了，这样你就可以把每个游戏都转化成 Nim ，然后根据上面的结论，只需要把 sg 函数异或起来，判断是否为 0 即可。
例题
正好在一个网站上看到了一道有趣的题，我就贴上来好了：
然后最近还做了一道题：agc043，这个对 sg 的应用挺基础的，倒是其他部分有点难度。
别的没了，网上那些博客例题超多，就是讲的不对