自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:49:19，当前版本为作者最后更新于2023-08-03 23:52:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑啥时候游戏停止，如果轮到某人他无法操作了，那么除非他手中的数为等差数列，否则对方的集合大小必然大于等于他的集合大小。更进一步的，大小为 $n$ 的正整数集合只有等差数列中两两数的差值才只有 $n-1$ 种不同可能，归纳法很好证明。

所以我们可以发现几乎所有情况下都是拥有数字多的一方获胜。或者说在大部分情况下，如果先手有 $n$ 个数字时：当后手拥有大于等于 $n$ 个数字的时候，后手必胜；当后手拥有小于等于 $n-1$ 个数字的时候，先手必胜。

接下来考虑少数情况，也即输家数字比赢家多，此时不妨假设输家最终 $\{a,a+d,\dots,a+(n-1)d\}$ 共 $n$ 个数，赢家最终 $\{d,2d,\dots,(n-1)d\}$ 共 $n-1$ 个数，此时输家操作。

当先手 $n$ 个数字时，后手 $n-1$ 个数字若满足上述情况则后手必胜。否则说明至少经过了一次操作才达成了上述关系，这也就说明存在 $t$ 满足 $a=td$（或者说 $a$ 必然是 $d$ 的倍数）。那么最终关系形如：输家为 $\{td,(t+1)d,\dots,(t+n-1)d\}$；赢家为 $\{d,2d,\dots,(n-1)d\}$。

注意到赢家在游戏结束时都只能构造出来 $d,2d,\dots,(n-2)d$ 这些数字，所以我们可以得出 $(n-1)d,nd,\dots,(t+n-1)d$ 必然不是后来加入输家集合的，而是一开始就在输家集合中的。

考虑 $t=1$ 的特殊情况，也即最终关系形如：输家为 $d,2d,\dots,nd$，而赢家为 $d,2d,\dots,(n-1)d$。在这种情况下，输家初始必然拥有 $(n-1)d,nd$。由此我们知道这种局面出现的必要条件之一便是输家一开始拥有 $(n-1)d,nd$ 且赢家一开始最大值小于等于 $(n-1)d$，并且所有人一开始拥有的数字都是 $d$ 的倍数。

事实上非常巧合的一点就是这个必要条件就是充要的，因为在这种条件下赢家总是可以操作，某次轮到赢家操作的时候不妨设赢家集合大小为 $m$，输家除了 $(n-1)d,nd$ 两个数以外小于 $(n-1)d$ 的数字只有 $m-2$ 个，而赢家总是可以构造出至少 $m-1$ 个小于 $(n-1)d$ 的数字。

于是我们知道少数情况也就两种，一种是先手本来拥有的就是等差数列而被后手卡死直接赢，另一种又分先后手，一种就是先手有 $n$ 个数，后手 $n$ 个数，存在一组 $N,d$，满足后手最大两个数为 $Nd$ 和 $(N-1)d$，且先手最大数小于等于 $(N-1)d$，且所有数均为 $d$ 的倍数，则先手必胜，一种就是先手有 $n$ 个数，后手 $n-1$ 个数，存在一组 $N,d$，满足先手最大的两个数为 $Nd$ 和 $(N-1)d$，且后手最大数小于等于 $(N-1)d$，且所有数均为 $d$ 的倍数，则后手必胜。

至于具体去计数也很简单，唯一比较困难的一个地方就是如何统计一开始先手就无法操作的等差数列，这个可以枚举公差 $d$，然后用 bitset 存所有数，每次与上自身右移 $d$ 位，$k$ 次操作得到的 $1$ 的数量就是长度为 $k+1$ 且公差为 $d$ 的等差数列数量，复杂度为 $O(a^2\log a/w)$。

综上，复杂度为 $O(a^2\log a/w+a\log a)$。