博弈论笔记。

SG 函数

终止态的 $SG$ 值为 $0$ 。

$SG (u) = \mathrm {mex} _ {(u, v)} {SG(v)}$ 。

多个独立游戏的 $SG$ 函数值为所有游戏的异或和。

先手必败当且仅当 $SG = 0$ 。

对于 Anti 规则，先手必败当且仅当：

经典模型

$n$ 个石子，两人轮流取，每次可以取 $[1, m]$ 个，不能取者败。

先手必败当且仅当 $(m + 1) | n$ 。

$n$ 个石子，两人轮流取，每次可以取 $[1, m]$ 个，不能取者胜。

先手必败当且仅当 $n \equiv 1 \pmod {m + 1}$ 。

$n$ 堆石子，两人轮流取，每次可以选择第 $i$ 堆取 $[1, a _ i]$ 个，不能取者败。

先手必败当且仅当 $\oplus _ {i = 1} ^ n a _ i = 0$ ，即对于二进制下每一位的和 $s$ 均满足 $2 | s$ 。

$n$ 堆石子，两人轮流取，每次可以选择第 $i$ 堆取 $[1, a _ i]$ 个，不能取者胜。

先手必败当且仅当：

$n$ 堆石子，两人轮流取，每次可以选择最多 $k$ 堆取任意多个，不能取者败。

先手必败当且仅当二进制下每一位和 $s$ 均满足 $(k + 1) | s$ 。

$n$ 个石子，两人轮流取，每个人可以取任意多个，但是不能取完，每个取的个数不能超过上个人取的个数的两倍，不能取者败。

先手必败当且仅当 $n$ 位斐波那契数。

$n$ 堆石子，两人轮流取，每个人可以选择第 $i$ 堆取 $[1, a _ i]$ 个放入第 $i - 1$ 堆中（第 $1$ 堆直接取走），不能取者败。

先手必败当且仅当 $\oplus _ {i = 0} ^ {\lfloor \frac {n - 1} 2 \rfloor } a _ {2i + 1} = 0$

$n$ 堆石子，两人轮流取，每次可以选择第 $i$ 堆取 $[1, a _ i]$ 个，或者将一堆石子分为不为空的两堆，不能取者败。

$a$ 个石子有 $sg$ 函数 $sg(a) = \begin{cases} a - 1, a \equiv 0 \pmod 4 \\ a, a \equiv 1, 2 \pmod 4 \\ a + 1, a \equiv 3 \pmod 4\end{cases}$

先手必败当且仅当 $\oplus _ {i = 1} ^ n sg(a _ i) = 0$ 。

$2$ 堆石子，两人轮流取，每个人可以选择一堆取任意多个或者两堆取相同个，不能取者败。

第 $k$ 个先手必败局面记作 $(a _ k, b _ k)$ ，$a _ k$ 为前 $k - 1$ 个 $a, b$ 没有出现的最小正整数，$b _ k = a _ k + k$ 。其中 $a _ 1 = 1, b _ 1 = 2$ 。

存在通项公式：$a _ k = \lfloor k \frac {1 + \sqrt 5} 2\rfloor$ 。

给定一个二分图，一个棋子，两人轮流将棋子在二分图的边上转移，不能到之前到过的点，不能转移者败。

先手必败当且仅当存在一种最大匹配方案，起点不被匹配。

给定一个 DAG ，一个起点，一个棋子，两人轮流将棋子在图的边上转移，不能到之前到过的点，不能转移者败。

先手必败当且仅当起点 $SG = 0$ 。

给定一个 $n$ 个点的有根树，两人轮流从树上删去一条边，并移除与根不连通的部分，无法删除者输。

$SG(u) = \oplus _ {(u, v)} (SG(v) + 1)$ 。

将树改为图，任何环内的节点可以融合成一点而不会改变图的 $SG$ 值。