Solution. 取石子游戏

Description

$n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子，颜色为 $c_i$。A 和 B 轮流行动，A 先手，每人有两种操作：

• 选择一堆石子并从中取出任意个石子。
• 选择一种颜色并从若干堆这种颜色的石子中取出不超过 $m$ 个石子。

不能不取。不能操作的人失败。

Solution

不同颜色的石子堆是独立的，所以考虑对每种颜色的石子堆单独考虑，然后再将 $SG$ 函数合并起来。

现在问题转化为，有若干堆颜色相同的石子，计算这个局面的 $SG$ 函数值。

第 $i$ 堆石子有 $a_i$ 个，设 $b_i=\lfloor\frac{a_i}{m+1}\rfloor,c_i=a_i\bmod (m+1)$，结论是，$SG$ 函数为：
$$
\left(\bigoplus_i b_i\right)\cdot(m+1)+\left(\sum_i c_i\right)\bmod(m+1)
$$
考虑归纳证明这个结论。对 $\sum a_i$ 进行归纳。

设 $P=\bigoplus_i b_i,Q=(\sum_i c_i)\bmod(m+1)$。

如果使用操作一，则 $P'$ 可以取到任意不大于 $P$ 的值，若 $P'<P$，则 $Q'$ 可以取任意值，否则我们不确定 $Q'$ 的取值范围，另外 $P',Q'$ 不可能同时不变。这样就证明了使用操作一可以转移到的状态的 $SG$ 函数值集合至少为 $[0,P(m+1)-1]$。

如果使用操作二，在 $P'=P$ 的情况下，我们显然可以让 $Q'$ 取到任意小于 $Q$ 的值，这样就补齐了 $[P(m+1),P(m+1)+Q-1]$ 的部分。

于是，当前状态的 $SG$ 函数值为 $P(m+1)+Q$，即开头提到的那个式子。

感性理解的话，操作一是 nim 博弈，操作二是 bash 博弈，所以 $SG$ 函数就是这两个基础博弈的缝合版。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。