博弈论

巴什博弈

$n$ 个棋子，2人互相取石子，一次最多取 $m$ 个，无法操作为输。
结论
$n\mod(m + 1) == 0$ 为先手必败态，否则先手必胜。

威佐夫博弈

2堆石子分别有 $x, y$ 个，2人互相操作，可以进行2种操作

1. 对任意一堆取 $x$ 个
2. 对2堆同时取 $x$ 个

$x$ 需要满足取的合法
无法操作为输。
结论
假设2堆石子数为 $(x, y)$ (其中 $x \le y$)
那么先手必败，当且仅当
$(y - x) * \frac{(\sqrt{2} + 1)}{2} = x$
其中 $\frac{\sqrt{2} + 1}{2} = 1.618$，就是黄金分割率！

Nim游戏

$n$ 堆石子，第 $i$ 堆有 $a_i$ 个，2人互相取石子，操作为对任意一堆取任意数量的石子，无法操作为输。
结论:
$a_i$ 异或和为零时先手必败态，否则先手必胜。

SG函数

先手必胜：当且仅当SG函数不为零 (当然递推也可以解决胜负)
$SG(u) = \text{mex}$ { $SG(v)$ } 。构建有向无环图, $v$ 代表 $u$ 的后继状态。
SG函数关键在于可以求取游戏的和
设置 $G_i$ 代表一种游戏,

• $G = G_1 + G_2 + G_i$
• 每次选择一个 $G_i$, 移动一步

SG函数厉害之处在于:
$SG(G) = SG(G_1) \oplus SG(G_2) \oplus SG(G_i)$

$mex$ 的经典求法——先用集合Set存下所有后继状态 $sg[v]$, 然后从 $0$ 开始枚举 $sg[u]$ 的取值

set<int> se;
se.insert({sg[v]});
while (se.count(sg[u])) sg[u] ++;