AT_arc148_d [ARC148D] mod M Game

tokitsukaze · 2026-06-12 18:24:37 · 题解

参考了 AT 官方题解里的这一篇。

Solution

设 S_A, S_B 分别表示两个人拿的数的总和，sum 为所有数的总和。

Bob 的获胜条件为：S_A \equiv S_B \pmod m。

又由于 S_A+S_B=sum，推出 2 \times S_A \equiv sum \pmod m。

将所有 a_i 乘 2，问题转化成，令 Alice 拿走 n 个数之和为 newS_A，如果 Bob 能够“操控” Alice 的操作，使得 newS_A \equiv sum \pmod m，Bob 就能赢。

考虑 Bob 如何”操控“。如果满足 newS_A \equiv sum \pmod m，说明 Bob 拿走另外 n 个数之和 newS_B 也会满足 newS_B \equiv sum \pmod m。也就是说，Bob 只要模仿 Alice 做镜像操作就能够尽可能地满足 newS_A \equiv sum \pmod m。

所以 Bob 要赢需要同时满足两个条件：

1. 每一步 Bob 都能够完成镜像操作。

所以实现上只需要统计 a_i \times 2 \bmod m 的出现次数的奇偶性，以及求出 sum 和 newS_A 进行判断。于是这个题就做完了。

可能会有人疑问：为什么要将所有 a_i 乘 2？

如果不乘 2，Bob 在某一步无法进行镜像操作的时候，并不一定会直接输掉。Bob 可能可以进行”错位匹配“。这样的话就会使得情况变得复杂，需要进行一些分讨。例子就是：

2 4
0 1 2 3