尼姆游戏（SG函数解决变形）

56 阅读 0 评论 37 点赞

我是靠谱客的博主悲凉便当，最近开发中收集的这篇文章主要介绍尼姆游戏（SG函数解决变形），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：
给定 $n$ 个石子堆，每堆有 $a_i$ 个石子（ $a_i>0$ ），每次可以选择一堆石子，从这堆石子中选择任意多的石子。两者皆采取最优策略，问什么状态下先手必败，什么状态下先手必胜。

题解：
经典尼姆游戏。
当 $a_1oplus a_2oplus a_3oplus ...oplus a_{n-1}oplus a_n=0$ ，先手必败。
当 $a_1oplus a_2oplus a_3oplus ...oplus a_{n-1}oplus a_nneq 0$ ，先手必胜。

证明：定义 $sum=a_1oplus a_2oplus a_3oplus ...oplus a_{n-1}oplus a_n$ 。
终态一定是所有石子堆的石子个数都为 $0$ ，即 $s u m = 0$ 时。

这里推测：

$s u m = 0$ 时，先手必败
$s u m \neq = 0$ 时，先手必胜

证明：
考虑先手处于必胜态时，此时 $s u m \neq = 0$ ，那么先手必然要拿掉一些石子使得后手面临必败态，即先手拿掉一些石子后使得 $s u m = 0$ 。
这里令被操作的石子堆是第 $i$ 堆，操作前的剩余 $n - 1$ 堆石子异或值为 $a_i$ ，若将第 $i$ 堆石子数量降至 $H$ ，则 $H \oplus H = 0$ ，此时后手将面临必败态。

问题转化为了寻找一个 $a_i$ ，使得 $a_i>H$ 。
这里对于 $s u m$ 的二进制最高位 $k$ ，必然也是一个数 $a_i$ 的二进制最高位，那么选择该 $a_i$ ， $H$ 必然比 $a_i$ 小，因此必然存在这样一个数使得 $a_i>H$ 。
证毕。

以上是对于经典尼姆游戏的证明。
那么若限制每次拿石子的个数为指定集合中的任意一个数，如何解决判断必败态和必胜态。

考虑 $S G$ 函数的构造。（具体的 $S G$ 函数介绍省略。）

直接给出结论：
令 $sum=SG(a_1)oplus SG(a_2)oplus SG(a_3)oplus ...oplus SG(a_{n-1})oplus SG(a_n)$
这里仍然推测：

$s u m = 0$ 时，先手必败
$s u m \neq = 0$ 时，先手必胜

考虑到 $S G$ 函数的定义， $SG(a_i)$ 可以到达任意小于 $SG(a_i)$ ，即上一个模型，证明与尼姆游戏的普通版本一样。问题转化为了如何求解 $S G$ 函数。

给出一个以 $f i b$ 数列作为可取石子的个数集合的 $S G$ 函数的模板： $h d u 1848 .$

int fib[17] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987};
int sg(int x) {
    if(~f[x]) return f[x];
    
    bool jud[M]; //M指的是需要的最大sg参数
    memset(jud, false, sizeof jud);
    for(int i = 1; i <= 15 && x >= fib[i]; ++i) jud[sg(x - fib[i])] = true;
    for(int i = 0; ; ++i) if(!jud[i]) return f[x] = i;
}