公平组合游戏
在任意确定状态下，所有参与者可选择的行动完全相同，仅取决于当前状态，与身份无关；
博弈中的同一个状态不可能多次抵达，博弈以参与者无法行动为结束，且博弈一定会在有限步后以非平局结束。
OI wiki 上是这么说的，大概意思就是说游戏双方可以干相同的事不会相互影响，一方无法行动结束了，并且会在有限步内结束。
每一个局面都有一个必胜必败态，如果它的后继状态中有一个必败态，则当前局面是必胜态；反之，如果后继状态没有必败态，则当前局面是必败态。
将局面放在图上向后继状态连边会形成 DAG。
Nim 游戏
游戏内容
有 \(n\) 堆石子，两人轮流取，每人每次只能选择其中一堆拿走任意多石子，但不能不拿，无法操作者输。
结论
求最开始每一堆石子个数的异或和，若不为 \(0\) 则先手必胜，否则必败。
证明
需证明异或和为 \(0\) 是必败态，不为 \(0\) 为必胜态。
首先若无法操作即所有堆个数均为 \(0\)，异或和显然为 \(0\)。
如果当前局面的异或和不为 \(0\)，考虑其最高位，则一定有一堆石子个数的二进制最高位和异或和的最高位相同，拿这堆石子即可让异或和重新为 \(0\)，即进入对方必败态。
如果当前局面异或和为 \(0\)，则无论取哪一堆，异或和都会变化，即进入对方必胜态。
SG 函数
SG 函数是用来描述当前局面的必胜必败状态的函数，其参数就是当前局面。
定义 \(SG(x)\) 为局面 \(x\) 的 SG 函数，若 \(x\) 有 \(k\) 个后继状态 \(y_1,y_2,\cdots,y_k\)，则：
容易发现结束局面没有后继状态，\(SG(x) = 0\)，进而发现如果一个局面的 \(SG(x) =0\)，则当前局面必败，否则必胜。
因为如果 \(SG(x)=0\)，也就是后继状态没有 \(SG(y) = 0\)，即必败态；若存在 \(SG(y)=0\)，则 \(SG(x)>0\)，能够转移到必败态，所以是必胜态。
SG 定理
其实如果只有 SG 函数这一个东西还不是很有用，还不如做一个必胜必败 DP，所以我们需要 SG 函数更优秀的性质。
内容
如果一个局面 \(x\) 能够划分成 \(k\) 个子局面 \(y_1,y_2,\cdots,y_k\)，则：
也就是我们可以用多个子局面的 SG 值拼出整个局面的 SG 值。
对于子局面，可以理解为 DAG 上几个不同的点，它们一起组成了当前局面。
证明
显然对于每一个 \(y_i\)，一定能够走到一个 \(SG(p) < SG(y_i)\) 的一个后继状态，但还有一些 \(SG(q)>SG(y_i)\) 的后继状态。
分类讨论，如果走到了一个 \(SG(q) > SG(y_i)\) 的后继局面，那么后手显然可以重新走到 \(SG(q')=SG(y_i)\) 的局面 \(q'\)，换言之，这是无效操作。
如果走到了 \(SG(p) < SG(y_i)\)，那么这就和 Nim 游戏本质相同了，每次可以让一个子局面的 \(SG\) 值减少任意值。
使用 Nim 游戏的结论即可得证。
例题
[ARC151D] Binary Representations and Queries
statement
显然每一个不同的全 \(0\) 段都是一个子局面，考虑分开讨论最后异或起来。
设 \(f_1(x),f_2(x),f_3(x),f_4(x)\) 表示两侧没有元素，只有一侧有元素，两侧元素相同，两侧元素不同的 SG 函数，我们写出转移方程：
打表发现：
计算出全局 SG 值即可。