组合游戏

定义

规则与 nim 游戏一样，唯一不同的是取走最后一个石子的人败。

先手必胜当且仅当：

分两种情况讨论：

所有堆石子都为 $1$ 。

显然先手必胜当且仅当堆数为偶数。
其他情况。
1. SG 不为 $0$ 的时候
若还有至少两堆石子数大于 $1$ ，先手将 SG 值变为 $0$ 即可；若只有一堆石子数大于 $1$ ，先手让状态变为奇数个 $1$ 。因此当 SG 函数不为 $0$ 的时候先手必胜。

有 $n$ 个物品，两个人轮流取，每个人至少选 $1$ 个至多选 $m$ 个，最后取光的获胜，判断先手是否有必胜策略。

我们用逆向思维，假设 $n=100,m=4$ ，那么谁先报到 $95$ ，那么不管另一个人报多少，他都必胜。同理谁先报到 $90,95,\cdots,5$ 谁就必胜。因此我们可以发现规律：

\operatorname{Bash}[n,m]=\begin{cases} n \mod (m+1) = 0 & \text{后手必胜} \\ n \mod (m+1) \ne 0 & \text{先手必胜}\end{cases}