SG函数
const int MAXN = 600000;
int n;
int sg[MAXN];
int SG(int x) {
// 默认值为-1
if(sg[x] != -1)
return sg[x];
bool used[32] = {};
// 这里写递归到后继状态
for(int i = 2; i < x; ++i) {
if(x % i == 0) {
used[SG(x - i)] = 1;
}
}
int res = -1;
for(int i = 0; i < 32; ++i) {
if(used[i] == 0) {
res = i;
break;
}
}
assert(res >= 0);
return sg[x] = res;
}
Nim博弈
有 \(n\) 堆石子，分别有 \(a_1,a_2,\cdots ,a_n\) 个，每次从一堆石子取 \([1,\infty]\) 个，不能操作的人输。
异或和为0时，先手必败，其余情况先手必胜。
若异或和为x，且x不为0，设x的二进制最高位为第k位，那么至少存在1堆石子ai其数量的第k位为1，易知ai xor x < ai，故可以从这堆石子中转移到异或为0的状态。
反之，假如当前异或和为0，那么无论怎么取，下一步异或和必定是非0值。
所以当异或和为0时，无论先手做什么，后手都能维持异或和为0的状态转移回来，直到胜利。反之先手可以把局面变成异或和为0的状态转移给后手。
总结：一堆石子的SG函数为 \(SG[n]=n\) 。
Bash博弈
有一堆石子，有 \(n\) 个，每次从一堆石子取 \([1,m]\) 个，不能操作的人输。
剩余石子为[1,m]时，显然是先手必胜，必胜策略是全取。
剩余石子为m+1时，是先手必败，无论第一步如何操作第二步都可以全取。
那么从[m+1+1,m+1+m]都是先手必胜，因为可以一步取到先手必败态。
故剩余石子为k(m+1)时，先手都是必败的，因为无论第一步先手取什么，后手都可以保持石子数为m+1的倍数。
总结：先手必胜当且仅当n不是m+1的倍数。一堆石子的SG函数为 \(SG[n]=n (\mod m+1)\) ，当有若干堆石子时，考虑SG函数。
公平组合游戏
双方均直到场上的所有信息，双方每一步能做的事情和当前轮是谁无关，同一局面不可多次到达，有限步内会结束，没有平局，无法行动的人输。多个公平组合游戏合起来也是一个公平组合游戏。
把公平组合游戏的每个状态看作节点，合法的决策是转移边，那么一个公平组合游戏就是一个DAG，出边为0的点（无法移动的点）是必败点，由于这是一个DAG所以可以通过DP求出所有的状态的胜负性。然后可以规定出SG函数：一个点的SG函数值为其后继点的SG值的集合的mex。
显然的结论：必败点的SG值为0，经过一次转移之后SG值必定改变，SG值不为0的点都是必胜点，因为其后继状态一定有一个是SG值为0的点。
不知道怎么证明的SG定理：若干个公平组合游戏的SG值，是他们一个一个的SG值的异或和。
使用SG定理解决的思路：观察哪个是一个单独的最小的公平组合游戏，对这个游戏进行打表，然后强行看出SG函数的规律。
Nim-k 博弈
有n堆石子，分别是a1,a2,...an个，每次从[1,k]堆石子取任意正数个，不能操作的人输。（Nim游戏是k=1的特殊形式）
当且仅当任意的k都有 \(k+1|\frac{\sum_{i=1}^n (2^k&a_i)}{2^k}\) 时先手必败，其余情况先手必胜。
Anti-Nim 博弈
首先不能操作的一方获胜。
必胜：SG函数非0且至少一堆石子数大于1，或SG函数为0且任意一堆石子数小于等于1。
Anti-SG 游戏
SG游戏中，首先不能操作的一方获胜。
必胜：SG函数非0且至少一个游戏的SG函数大于1，或SG函数为0且任意一个游戏的SG函数小于等于1。
Wythoff 博弈
二分图博弈
起点有一颗棋子，转移图是一个二分图，当起点在所有二分图的最大匹配中时，先手必胜。否则先手必败。