题解：AT_arc148_d [ARC148D] mod M Game

ww0707 · 2026-11-10 21:29:47 · 题解

Solution

显然博弈论，考虑从最后的局面开始分析这道题。

因为一共有 2N 个数，所以不妨加上最后只有两个数分别为 a 和 b。

并设当前两人分别拿的数之和为 x 和 y。

那么作为先手的 Alice 肯定有两种选择，若两种选择都无法让 Alice 赢才会让 Bob 赢。

于是有 a+x\equiv b+y\pmod{M} 并且 b+x\equiv a+y\pmod{M} 时Bob 会赢。

于是可得有 a-b\equiv b-a \pmod{M}。

推得满足条件需要有 a-b\equiv b-a \equiv 0 \pmod{M} 或者 a-b\equiv b-a \equiv \frac{M}{2} \pmod{M}。

那么不妨将满足条件的一对数 a,b 称作为配对的。

所以后手每次去取先手取的数所对应的那个数即上面成为配对的数就是最优策略。

显然若两两相等的数抵消后，若还有数则必须满足第二项能匹配完，此时有 M 为奇数时必定无解。

由于有 a-b\equiv b-a \equiv \frac{M}{2} \pmod{M}，所以为了最后的配对，必须满足第二种有偶数对。

接着考虑证明不满足时必定无解。

依旧先让两两能匹配的数抵消后，那么这时候先手不管是选什么后，都相当于与后手交换了真正的选取顺序，即 Alice 把必败的局面给了 Bob，则又回到了开始的问题，参考其他题解也有相当于 Alice 用 Bob 本来准备用来打败 Alice 的方法打败了 Bob。即先手也做能配对则配对的方法。

于是直接做即可，代码很短而且码风比较清奇就不展示了。