本文引用：https://oi-wiki.org/math/game-theory/impartial-game/
SG定理的介绍
定义mex函数的值为不属于集合S中的最小非负整数，即：
\[mex(S) = min\{x\}\quad(x\notin S,x\notin N) \]例如mex({0, 2, 3}) = 1,mex({0, 1, 2, 4}) = 3。
对于状态x和它的所有k个后继状态y_1,y_2,...,y_k,定义SG函数：
\[SG(x) = mex\{SG(y_1),SG(y_2),...mSG(y_k)\} \]对于由n个有向图游戏组合的组合游戏，设他们的起点分别为s_1,s_2,...,s_n,则有定理：
\[当且仅当SG(s_1)\oplus(s_2)\oplus...\oplus SG(s_n)\neq 0时，这个游戏是先手必胜的。\\同时，这是一个组合游戏的游戏状态x的SG值 \]这一定理被称作Sprauge-Grundy定理，简称SG定理。
SG定理的应用
SG定理适用于 任何公平的两人游戏，它常被用于决定游戏输赢的结果
计算给定状态的 Grundy 值的步骤一般包括：
- 获取从此状态所有可能的转换
- 每个转换都可以导致一系列独立的博弈（退化情况下只有一个）。计算每个独立博弈的Grundy值并对它们进行异或求和。
- 在为每个转换计算了Grundy值后，状态的值是这些数字的mex
- 如果该值为零，则当前状态为输，否则为赢
写不下去了，放个链接自己看吧：https://blog.csdn.net/a_forever_dream/article/details/104813148
标签：...,游戏,定理,博弈论,Grundy,SG,mex From： https://www.cnblogs.com/lyx9785/p/18410750