博弈论与SG函数¶

NIM 游戏¶

有 \(n\) 堆石子，每堆石子的个数分别为 \(a_1,a_2,\dots,a_n\) ，A与B轮流进行操作，每次选取未取完的一堆取走任意颗石子，先取完所有石子的人获胜，若先后手二人均执行最优策略，求胜者。

可以发现：假设任意状态下所有石子的异或和不为 \(0\) ，我们总有操作能使得异或和为 \(0\) （通过更改为异或和贡献最高位 \(1\) 的那个数的值）。而当异或和为 \(0\) 的时候，我们如何操作都不能使得异或和不为 \(0\) 。（除非不取石子，但这是非法的）

因此我们能够判断出，若行动时状态为所有数异或和为 \(0\) ，则有必胜策略。那么若初始异或和为 \(0\) 则是A胜，否则是B胜。

我们把石子的个数抽象为一堆石子所在的状态，称此状态的值为 SG 值。

我们定义失败状态的 SG 值为 \(0\) 。（如同取光的石子）

其余状态的 SG 值这样计算：

对于状态 \(X\) ,若其能到达的后续状态为 \(X_1,X_2,\dots,X_n\) ，则有

\[ SG(X) = mex\{SG(X_1),SG(X_2),\dots,SG(X_n)\} \]

这样定义以后，一个状态能够到达所有 SG 值比自己小的状态，正如取石子时能够取到所有石子数比当前少的状态一样。

而部分能到达 SG 值比自己多的状态的，对手只需再取回相同状态即可，故为无效的操作。

藉由此方法，问题又转化为了 NIM 游戏，只需判断 SG 值的异或和即可。

例题：CF2004E