AtCoder ARC148D – mod M Game 题解与思路重现

AtCoder Regular Contest 148 D – mod M Game

鲁莽的尝试？

一个非常显然的 Bob 的必胜局面是：对于任意 $x\in \{0,1,\cdots,M-1\}$，在这 $2N$ 个数中的出现次数均为偶数。由此 Bob 可以选择与 Alice 上一轮选的相同的数而获胜。

那……其他局面就一定是 Alice 必胜么？

我们只依靠该结论交一份代码。不出意料，没有通过。不过它只错了两成的测点！看来大体方向是正确的。

正解

Bob 必胜的必要条件之一是：存在将给定的 $2N$ 个数分成两部分，每部分均包含 $N$ 个数，且有两部分的和在 $\bmod M$ 意义下相同的方案。

对于任何 $M$，$N=1$ 的情况都是平凡的。从 $N=2$ 入手。令 Alice 首次选择的数为 $y$，Bob 在此前提下的最优解为选择 $b$。令在某种可能的最优方案中，二者随后选择了 $z,c$。则必然有
$$\begin{aligned}
&b+c\equiv y+z\pmod M&(1)\\
&b+z\equiv y+c\pmod M&(2)
\end{aligned}$$

这是因为 Alice 是先手，其目标是不让 Bob 顺利取完符合要求的划分集合。于是 Alice 取 $z, c$ 中的任意一个，最终剩余的数都可使得 Bob 的集合与之构成同余。由 $(1)+(2),(1)-(2)$ 分别得到：
$$\begin{aligned}
c-z&\equiv z-c&\pmod M&&c+2b+z&\equiv c+2y+z&\pmod M\\
2c&\equiv 2z&\pmod M&&2b&\equiv 2y&\pmod M
\end{aligned}$$

当 $2\not\mid M$ 时，存在 $2$ 的逆元，故而等式两侧同时乘 $2^{-1}$ 得到 $y\equiv b,z\equiv c$。若 $2\mid M$，则每个方程均有两类解：$b\equiv y+\frac{M}{2} \lor b\equiv y\pmod M$，$z,c$ 亦然。由于 $y$ 不确定，则对于任意 $y$ 以及其剩余集合构成的 $z,c$，均能够让 Bob 构造满足上述条件。

考虑 $N=3$ 的情况。令前两轮 Alice, Bob 分别取 $x, a$。则取完前两轮后问题递降为 $N=2$ 之情况。则对于任意初始的 $x$，仍应当存在 $2a\equiv 2x\pmod M$，以此类推。

那么我们可以得到如下策略：当 Alice 取 $x$，Bob 可以取满足 $2x\equiv 2a\pmod M$ 的任意 $a$。可以发现，假设在这两轮之前有 Alice 的和 $S=$ Bob 的和 $T$。如果 Bob 取 $a=x$，则仍有 $S\equiv T$；（在 $2\mid M$ 时）否则若 $a\equiv x+\frac{M}{2} \pmod M$，则当之后存在任意两轮，Alice 取 $y$ 而 Bob 取 $b=y+\frac{M}{2}\pmod M$，必然使得 $a+b\equiv x+y\pmod M$，有 $S’\equiv T’$。否则没有别的满足上述方程的解，Bob 必败。

（假如对于 $N=2$ 的情况，有不满足 $y\equiv b, z\equiv c$ 的方程 $y+z\equiv b+c\pmod M\quad\text{(i)}$。令 $y\equiv b+\Delta\iff z\equiv c-\Delta\pmod M$，则 Alice 只要取 $y, c$，逼迫 Bob 取 $z, b$，就会使得 Bob 的必胜条件变成 $y+z+\Delta\equiv b+c-\Delta\pmod M\quad\text{(ii)}$，当且仅当 $2\mid M,\Delta=\frac{M}{2}$ 时，$\text{(i),(ii)}$ 才能同时成立。）

同时我们还注意到，Bob 选取 $a=x+\frac{M}{2}\pmod M$ 时，必须能够与之后的某两轮配对。这就意味着若 $2\mid M$，让 $x$ 与 $x+\frac{M}{2}\pmod M$ 两两配对，配对总数应当为偶数，方有 Bob 必胜。当 $2\not\mid M$ 时必然只能有 $x$ 的出现次数为偶才有解。

利用 std::map 统计即可。时间复杂度 $\operatorname{O}(n\log n)$。

Submission #34806024