NIM游戏及其证明
题目描述即为T1，不多赘述
有向图游戏及SG函数
而对于由\(n\)个有向图游戏组成的组合游戏，设它们的起点分别为\(S_1, S_2, \ldots, S_n\)，则有定理：
当且仅当\(\text{SG}(s_1) \oplus \text{SG}(s_2) \oplus \ldots \oplus \text{SG}(s_n) \neq 0\)时，这个游戏是先手必胜的。
考虑如何证明，我们考虑NIM游戏中一种合法的取法为选择一堆并取走其中任意大于0的石子数也就是可以从 \(a_i\) 转移到 \([a_i-1,0]\) 的任意值，并且NIM游戏时通过当所有 \(a_i\) 都为0时游戏为先手必输而推来的，如果满足这个两个条件就可以沿用NIM游戏的定理
我们考虑 \(SG(x)\) 的定义，就是与 \(x\) 直连的所有后继的 \(mex\)，所以 \(SG(x)\) 可以直接转移到 \([SG(x)-1,0]\)，并且当所有 \(SG(a_i)\) 都为0时，游戏也是先手必输局面，这显然也满足NIM游戏的定义，所以可以直接沿用NIM游戏的证明，证毕
同时有意思的一点是，NIM游戏也可以用SG函数来解释，我们有k堆相当于有k个起点，然后对于每个堆可以拿走任意个的限制就是对于 \(a_i\)，它所对应的节点 \([a_i-1,0]\) 都有一条有向边，所以 \(SG(a_i)=a_i\)，也恰恰符合了定义
标签：游戏,NIM,题解,博弈论,ybt,text,oplus,SG From： https://www.cnblogs.com/zcxnb/p/18619051