自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 22:58:41，当前版本为作者最后更新于2025-07-21 00:48:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我居然过了以后没写这题题解诶？来补了来补了。

话说这题当时我写的时候还没有题解来着，怎么转眼这么多了。

只看每个点的移动是不好做的，我们试图想一个办法描述当前局面并从中寻找性质。

一个很好的方法是用点与点之间的间隔数来描述，每个棋子移动时都会减少左侧的间隔，并在右侧扩大相同的数目。

如果你学习过阶梯 nim 并做过 P3480，那么你已经会做了。

把每个间隔看成一堆有着对应数目的石子，每次操作会从左侧拿取若干并放到右侧的堆中，最后把所有石子堆在最右侧的人获胜。

这就是阶梯 nim 最标准的形式啊！

根据阶梯 nim 的经典结论我们知道：先手必败当且仅当奇数堆中的石子数异或和为 $0$。

套结论就做完了，代码略。

不给证明会被骂的吧。

我们注意到如果必败方对偶数堆进行操作，必胜方一定可以再移回偶数堆。

于是偶数堆没用，移到偶数堆相当于弃置。

那么奇数堆就等价于可以任意拿走若干石头，此时就是标准的 nim 游戏的形式了。

证明完毕。