SG 定理

SG 定理用来解决有向图游戏：在有向图上一次走一步，不能继续走的玩家获胜。定义 SG 函数为

$$SG(x):={\mathrm{mex}}_{x\to y}\{SG(y)\},$$

则先手获胜当且仅当所有起点 $s_i$ 的 SG 函数的异或和非 $0$，即

$$\underset{i}{⨁}SG(s_i)\ne 0.$$

这里实际上是说，如果有两个独立的有向图，并且每个玩家每次都可以随意选择一张图上走一步，那么整张图的 SG 函数值等于这两个子图的函数值的异或。

TIPS

这类题目应当积极打表，很可能发现规律。