CF1404D Game of Pairs 题解

考虑先写个暴力 dfs 程序打表，可以发现下面的关键结论：

• 若 $n$ 是偶数，则先手必胜。
• 若 $n$ 是奇数，则后手必胜。

下面考虑证明结论：

$2\mid n$

打表可以发现先手把 $i,i+n$ 两个元素分为一组，此时后手无论在第 $i$ 组里选择 $i$ 还是 $i+n$，其在对 $n$ 取模意义下都相当于是增加了 $i$。而 $\sum\limits_{i=0}^{n-1}i=\frac{n(n-1)}2=\frac{n^2-n}2\not\equiv 0\pmod n$，因此模 $2n$ 显然也无法整除，也就是无论后手怎么操作，先手都是必胜。

$2\nmid n$

可能是一个不太一样的角度？考虑到 $2n$ 个数中 $\bmod\ n$ 值为 $0,1,2,\ldots,n-1$ 的数都恰好有 $2$ 个，因此一旦后手存在一种方案恰好选取了 $\bmod\ n$ 值为 $0,1,2,\ldots,n-1$ 的数各一个，则这些数的和 $\bmod\ n$ 一定为 $0$。又因为此时所有数的和 $\bmod\ 2n$ 的值一定为 $n$，因此若这样的方案 $\bmod\ 2n$ 的值为 $n$，则选剩下所有没被选的数即可使得和 $\bmod\ 2n$ 的值为 $0$。

然后考虑证明无论先手怎么给元素分组，后手都可以给出一个这样的策略：

设当前组两个元素的值为 $(i,j)$，则：

• 若 $i\equiv j\pmod n$，则选哪一个元素都不会影响 $\bmod\ n$ 的值，直接忽略。
• 否则，给每一组的元素 $\bmod\ n$ 的值之间连一条边，则图一定由若干个不相交的简单环组成。考虑找到连接 $i\bmod n$ 和 $j\bmod n$ 两个元素的值，则顺着这个环绕一圈每一次选择相同方向的端点一定能恰好取遍环上所有 $\bmod\ n$ 的值。

因此可以证明此时后手一定存在一组恰好取完值 $\bmod\ n$ 后为 $0,1,2,\ldots,n-1$ 的方案，此时后手一定可以胜利。