Content：博弈论
Date：2025.8.2

课堂内容

SG 函数

表示当前游戏局面的函数，后手必胜当且仅当 SG 函数为 0。

多个游戏的组合的 SG 函数为每个游戏的 SG 函数的 异或和。

经典模型

取石子游戏

题目描述

有 $n$ 堆石子，A、B 轮流取，每次从任意一堆中取出至少一个石子，不能取的输，问谁赢。

解法

一堆大小为 $n$ 的 SG 函数为 $n$ ，根据 SG 函数的性质，可以发现整个游戏的 SG 函数为 $\displaystyle \bigotimes_{i=1}^n SG_i$ 。

阶梯取石子游戏

题目描述

有 $n$ 堆石子放在台阶上，A、B 轮流取，每次从任意一堆中取出至少一个石子，放到下一个台阶上（如果在第 1 个台阶，则扔掉），不能取的输，问谁赢。

思路

可以发现最后的答案之和奇数层的石子有关，所以整个游戏的 SG 函数为所有奇数层 SG 函数的异或和。

树状取石子游戏

题目描述

在一颗大小为 $n$ 的树上有 $n$ 堆石子，A、B 轮流取，每次从任意一堆中取出至少一个石子，移动到他的父亲节点（如果在 1 号节点，则扔掉），不能取的输，问谁赢。

思路

跟上面的其实是一样的，只不过这里的答案只跟奇数层的节点的 SG 函数的异或和有关。

Bash 博弈

题目描述

有 $n$ 堆石子，A、B 轮流取，每次从任意一堆中取出至少一个石子，至多取 $m$ 个，不能取的输，问谁赢。

思路

每个石子堆的 SG 函数为 $n \bmod (m+1)$ ，异或起来即可。

1-动态减法游戏

题目描述

有一个正整数 $n$ ，A、B 轮流在上面减去一个数，第一个人至多减 $n-1$ ，后面每个人减的数不超过上一次的，最先吧这个数减到 0 的人获胜。问最后谁赢。

思路

先手每次都可以取原数的 $lowbit$ ~~（人类智慧）~~，所以后手必胜当且仅当 $n = 2^k$ 。

2-动态减法游戏

题目描述

有一个正整数 $n$ ，A、B 轮流在上面减去一个数，第一个人至多减 $n-1$ ，后面每个人减的数不超过上一次的两倍，最先吧这个数减到 0 的人获胜。问最后谁赢。

思路

对原数进行斐波那契分解，先手每次取最低位的 1 ~~（人类智慧 $\times$ 2)~~，所以后手必胜当且仅当 $n$ 为斐波那契数。

k-动态减法游戏

题目描述

有一个正整数 $n$ ，A、B 轮流在上面减去一个数，第一个人至多减 $n-1$ ，后面每个人减的数不超过上一次的 $k$ 倍，最先吧这个数减到 0 的人获胜。问最后谁赢。

思路

只需要一种满足任何表示方法中最低非零位的值的 $k$ 倍小于次低非
零位。
每次将新加入的数设为前面的数能表示的最大值 $+1$ 即可 ~~（人类智慧 $\times$ 3）~~。

NimK 游戏

题目大意

有 $n$ 堆石头，A、B 轮流取，每次从至多 $k$ 堆中取出至少一个石头，不能取的输，问最后谁赢。

思路

求 SG 函数在 $k+1$ 进制下的不进位加法。

Anti-Nim 游戏

题目大意

同 普通取石子游戏规则，但是不能操作的人胜利。

思路

先手必胜的条件为：

SG 函数的和为 0 且所有游戏的 SG 函数的值均不大于 1；
SG 函数的和不等于 0 且至少一个游戏的 SG 函数值大于 1。

例题

AGC017-D Game On Tree

思路

对于每一个子树，其 SG 函数为所有子节点的 SG 函数加上一条边的状态，即 $\displaystyle SG_u = \bigotimes_{v \in son(u)} (SG_v + 1)$ 。

提交记录：link