博弈论
Nim游戏
对于 \(n=2\)，\(a_1=a_2\)，后手可以“模仿”先手，使得后手必胜。
对于 \(a_1\ne a_2\)，先手可以让自己进入“模仿期”，使得先手必胜。
结论：若 \(\oplus a_i=0\)，先手必败，否则必胜。
很神奇的东西，证明需要群论知识。
发现石子的合并满足上面四条性质，所以石子的合并就是异或。
**严谨的证明
对于局面 \(\{a_i\}\)，这个局面的状态已经确定，因为两人都是极其聪明的。
证明很厉害，利用异或来进行证明，咕。
将获胜条件变为“不能操作者获胜”。
博弈论往往都是从小规模的问题出发找规律。
当 \(a_i\le 1\) 时，特殊讨论。其余情况与前面结论一致。
特殊讨论：令 \(s=\oplus a_i\)，\(s\leftarrow s\oplus 1\)。
SG函数
公平组合游戏
局面直接决定了先手是否必胜。
若先手必胜，称为 \(N\) 型局面，否则为 \(P\) 型局面。
根据定义，局面的转移关系构成 DAG。
注意，公平组合游戏必须是“无法行动者输”
SG 值定义为所有能直接转移到的局面的 mex.
两个局面合并后产生的新局面的 SG 值为原先两个局面的异或。
对于 Nim 游戏来说，每个 \(\{a_i\}\) 有一个 SG 值，将 \(\{a_i\}\) 合并起来后即为异或。
若 SG 为 \(0\) 先手必败，否则必胜。
任何公平组合游戏都可以用 SG 值刻画
HNOI2007 分裂游戏
后面听了点，不想记了。
标签：局面,游戏,必胜,异或,数学,整合,day4.2,oplus,SG From： https://www.cnblogs.com/BYR-KKK/p/18173538