The Subtraction Game
Nim 游戏。每一次可以从某一堆里面取走至多 $k$ 个石头，不能操作者输。
每一堆的是独立的，所以局面的 sg 值是每一堆的 sg 值的异或和。此外，不难发现一个包含 $n$ 个石头的堆的 sg 值为 $n \pmod {k+1}$。
Greedy Nim
不能操作者输
Nim 游戏。每次只能从石头个数最大的堆中拿石头。不能操作者输。
设当前单个堆中石头个数的最大值为 $m$，次大值为 $n(n < m)$，石头个数最大的堆数为 $p_m$，石头个数次大的堆数为 $p_n$。
结论是，$p_m$ 为奇数时是必胜状态，否则是必败状态。
必胜状态可以转移到必败状态：
- $p_m = 1$
- 通过决定操作后那堆石子剩下的数量是等于 $n$ 还是小于 $n$ 来调整 $p_n$ 的奇偶性。
- $p_m > 1$
- 任意操作即可
必败态只能转移到必胜态：
- 必败态中 $p_m \ge 2$，所以操作后 $p_m \ge 1$ 且为奇数
不能操作者赢
没有找到相关的资料，所以下面是我自己口胡的。
Nim 游戏。每次只能从石头个数最大的堆中拿石头。不能操作者赢。
仍然设当前单个堆中石头个数的最大值为 $m$，次大值为 $n(n < m)$，石头个数最大的堆数为 $p_m$，石头个数次大的堆数为 $p_n$。
结论是，以下状态为必胜状态：
- $m=1$ 且 $2\mid p_m$
- $m\neq 1$ 且 $2\nmid p_m$
必胜状态可以转移到必败状态：
- $m=1$：显然
- $m=2$：
- $p_m > 1$：随意操作即可
- $p_m = 1$：通过决定把操作的石头堆拿到只剩下 $1$ 还是只剩下 $0$，达到决定操作后 $p_1$ 的奇偶性的目的
- $m=3$：
- 证明同“不能操作者输”
必败状态只能转移到必胜状态：
- $m=1$：显然
- $m> 1$：因为 $p_m \ge 2$，所以不可能转移到 $m=1$ 的状态，所以只可能转移到 $m> 1$ 的必胜态
阶梯Nim
每一次可以从第$i(i>1)$堆中拿若干个放到第$i-1$堆里面，或者从第$1$堆里面扔掉若干个，不能操作者输。
等价于对编号为奇数的堆做Nim游戏。
如果第一个人操作了偶数堆，那么第二个人可以把第一个放进那个奇数堆的石子放进后面的偶数堆，这样奇数堆的状态不变。所以偶数堆可以直接当做“垃圾桶”用。
每一个人都按照奇数堆的必胜策略操作即可。
一个变形是挪硬币游戏：$1\times n$ 的方格中，若干个格子上有硬币。每次可以选择一个硬币、往左移若干格（要求保证跨过的位置都没有硬币），不能操作者输。
可以把硬币之间的间隙看作石头堆，转化成阶梯 Nim 游戏。
Nim-K游戏（Moore’s Nim-K）
参考 这篇博客
不能操作者输
有$n$堆石子，每次可从至多$k$堆中拿走任意数量的石子，不能不拿。不能操作者输。
把每堆的石子数用二进制表示，如果每一位上$1$的个数$\pmod {k+1}$都是$0$则先手必败，否则先手必胜。
证明：
如果是必败态，那么由于每一位上都至多有$k$个数被改变，所以转移到的一定是必胜态。
下面证明从必胜态可以转移到必败态。从高位到低位依次调整，显然在调整高位的时候用过的那些堆，在当前这一位是可以任意取值的。设用过的堆有$m$个，去掉这$m$堆之后还有$s$堆在这一位上是$1$：
- 若$s + m \le k$，我们可以直接对那$s$堆进行操作，这样进行过操作的总堆数不会超过$k$。
- 否则$s+m > k$，也就是说$m > k - s$，也就是说$m\ge k+1-s$，所以可以直接将$m$中的$k+1-s$堆设置为$1$，其它的设置为$0$，使得这一位上的$1$的总数为$k+1$的倍数。
不能操作者赢（Mis`ere Nim-k)
有$n$堆石子，每次可从至多$K$堆中拿走任意数量的石子，不能不拿。不能操作者赢。
只有两种可能的必胜局面：
- 每堆里面都只有一个石头，并且堆数 $\pmod {K+1} \neq 1$。
- 每堆的石头个数不全为 1，且存在某个二进制位上 1 的个数 $\pmod{K+1} \neq 0$
对应的，必败局面为：
- 每堆里面都只有一个石头，并且堆数 $\pmod {K+1} = 1$。
- 每堆的石头个数不全为 1，且每个二进制位上 1 的个数 $\pmod{K+1} = 0$
必败态只能转移到必胜态：
- 该局面存在石头个数大于 1 的堆
- 不能转移到必败态 2. ：一次操作至多只能改变 $K$ 堆石头，但是这样的转移需要让某一位的 1 的个数减少 $K+1$
- 不能转移到必败态 1. ：由于存在石头个数大于 1 的堆且每个二进制位上 1 的个数都是 $K+1$ 的倍数，所以石头个数大于 1 的堆的数量一定不小于 $K+1$，所以一定不可能转移到每堆石头的个数都是 1 的状态
- 该局面所有堆的石头个数都是 1 且石头总数大于 $K+1$
- 不能转移到必败态 2. ：每堆中石头的个数只会减小
- 不能转移到必败态 1. ：这需要操作 $K+1$ 堆石头
- 该局面所有堆的石头个数都是 1 且石头总数等于 $1$
- 拿走这唯一的一个石头之后，给对方的是必胜状态（终态）
必胜态可以转移到必败态：
- 存在石头个数大于 1 的堆
- 石头个数大于 1 的堆的数量不超过 $K$：可以转移到必败态 1.
- 石头个数大于 1 的堆的数量超过了 $K$：按照“不能操作者输”的策略进行操作，可以转移到必败态 2.
- 所有的堆的石头个数都是 1：
- 可以通过拿走不超过 $K$ 堆来转移到必败态 1.
Fibonacci Nim
有一堆石子，双方轮流取石子：第一轮中，先手不能一次性把所有的石头取完；以后的每一轮中，玩家取的石头数不能超过上一轮中对手取的石头数的2倍，至少要取一颗石头。
结论是，当石头数为斐波那契数的时候，先手必败，否则先手必胜。
k 倍减法 Nim
参考：
- NOI2009 冬令营论文 《从“k 倍动态减法游戏”出发探究一类组合游戏问题》
- SovietPower 的博客
- 朝拜明天19891101的博客
题目：poj3922 A simple stone game
有一堆石子，石子的数量为 $n$，双方轮流取石子：第一轮中，先手可以取任意多个，但是不能取完；以后的每一轮中，玩家可以取的数量不能超过上一个人取的石头数量的 $k$ 倍。不能操作者输。问谁会赢。
做法 1
考虑 $f_i$ 表示石头的总数为 $i$ 时，上一轮中取掉的石头个数至少是多少，这个状态是必胜态。注意到 $f_i \le \lceil \frac{i}{k} \rceil$。则 $f_i = \min\{ \lceil \frac{i-j}{k} \rceil, (i-j)k < f_j\}$。
注意到 $(i-j)k < f_j$ 也就是 $ik < f_j + kj$，要求 $\lceil \frac{i-j}{k} \rceil$ 最小也就是要求 $j$ 最大，所以我们用个单调栈维护 $f_j + kj$ 即可。
时间复杂度 $O(n)$。
做法 2
如果我们知道 $n$ 颗石头是必败态，那么可以推得：
- $n+1, n+2, \cdots n+x(xk < n)$ 是必胜态
- 对于 $n + x (xk \ge n)$，这个状态的胜负取决于谁能拿到 $x$ 个石头中的最后一个石头
所以我们可以维护必败状态集合，初始 $S = \{ 2, 3, \cdots k+1\}$。每次取出 $S$ 中最大的元素 $n$，找出最小的必败的 $x \ge \lceil \frac{n}{k} \rceil$，将 $n+x$ 加入集合。注意到这样找出来的 $n+x$ 一定是 $>n$ 的最小的必败状态。
复杂度 $O(\log_{\frac{k+1}{k}} n)$。
翻硬币游戏
参考 IOI2009 贾志豪的论文。
有一些关于翻的硬币的限制（例如，硬币排成一排，要求翻转的必须是长度为 $k$ 的一段），并且要求翻的最右边（二维的时候则是右下角）的硬币必须是从正面到背面，不能操作者输。
结论是，局面的 sg 值等于每个正面朝上的硬币单独存在时的游戏的 sg 值的异或和。
可以考虑一个这样的游戏：每次可以拿走一个石头，并且按照限制在别的地方放入一些石头（例如，一排方格，拿走某个石头，并且在左边的 $k-1$ 个格子都放入一个石头）。如果某个位置的石头个数是偶数，那么拿走那个位置的石头是没有意义的（因为后手可以模仿先手的操作）；所以这个游戏和翻硬币游戏是等价的（因为放入一个石头也就是反转了“这个格子是否会被操作”）。并且，这个游戏中每个石头显然是独立的，我们算出每个石头的子游戏的 sg 值异或起来，得到的就是整个游戏的 sg 值。
删边游戏 Green Hackenbush
参考：IOI2009贾志豪论文，以及 Winning Ways for Your Mathematical Plays, Vol1, Chapter 7 Hackenbush。
给一张无向图，其中有一个点为根。每次操作可以删去一条边，并拿走操作之后不与根连通的部分。不能操作者输。
结论：
- 树的删边游戏：叶子节点的 SG 值为 0；中间节点的 SG 值为它的所有子节点的 SG 值加 1 后的异或和。（这里的“某个点的 SG 值”指的是这个点的子树内的点构成的子游戏的 SG 值）
- 无向图的删边游戏：（Fusion Principle）不断把图中的任意一个偶环缩成一个新点，任意一个奇环缩成一个新点和一个自环，所有连到原先环上的边全部改为与新点相连，这样的改动不会影响图的 SG 值。最终转化成树的删边游戏。
Anti-SG游戏
Anti-Nim游戏 (Mis`ere Nim)
有$n$堆石子，每次操作可以从某一堆中拿走至少一个石子。两个人轮流操作，不能操作者胜。
一个状态为必胜态，当且仅当下列两个条件有一个成立：
- 所有堆的石子个数为$1$，且石子个数的异或和为$0$。
- 存在一个堆的石子个数大于$1$，且石子个数的异或和不为$0$。
证明：
- 如果每一堆的石头个数都是$1$，每个人每一次都必须取完一堆，所以堆数是偶数的时候先手胜，否则后手胜。
- 存在至少一个石子数大于$1$的堆：
- 只有一个堆的石子数大于$1$：显然此时石子个数异或和不为$0$。先手可以选择把这一堆的石头取完或者取到只剩下一个，留给后手奇数个石子数为$1$的堆，所以这种状态先手必胜。
- 至少有两个堆的石子数大于$1$：如果此时的石子数异或和为$0$，则只能转移到存在至少一个石子数大于$1$且石子数异或和非$0$的状态；而若异或和非$0$，则一定存在一种转移方法可以转移到至少有两个堆的石子数大于$1$且石子数异或和为$0$的状态。
Anti-SG游戏
无法继续转移的人获胜。其余规则与SG游戏相同。
则有类似的结论：先手必胜当且仅当下列两个条件中有至少一个被满足：
- 所有单一游戏的SG值为$1$，且它们的SG值的异或和为$0$；
- 存在单一游戏的SG值不为$1$，且它们的SG值异或和不为$0$。
可以用与SG定理证明相似的方法，证明游戏与Nim游戏等价，从而推出结论成立。
参考资料
贾志豪论文