题解：AT_arc148_d [ARC148D] mod M Game

· · 题解

题意概述：

给定一个整数 m 和 2n 个小于 m 的整数 a_1,a_2,\dots,a_{2n}。Alice 和 Bob 进行游戏，Alice 先手，双方轮流删除一个数，直到这 2n 个数全部删除。游戏结束时，令 s_a 表示 Alice 删除的数之和，s_b 表示 Bob 删除的数之和。如果 s_a\bmod M=s_b\bmod M，则 Bob 获胜，否则 Alice 获胜。假设双方都采取最优策略，求最终谁会获胜。1\le n\le2\times10^5,2\le m\le10^9,0\le a_i<m。

不难发现，最终一定是 Alice 删除倒数第二个数，Bob 删除最后一个数。因此，设 Alice 删除倒数第二个数之前，删除的数之和为 x，Bob 删除最后一个数之前，删除的数之和为 y，最后剩下的两个数分别为 a,b。

那么，当且仅当 x+a\equiv y+b\pmod m 且 y+a\equiv x+b\pmod m 时，Alice 无论怎样选择都必败，故 Bob 必胜；否则 Alice 必胜。

两式相加：x+y+2a\equiv x+y+2b\pmod m\Rightarrow 2a\equiv 2b\pmod m。

由于 a,b<m，因此 2a,2b<2m，故 2a\equiv 2b\pmod m 只会有三种情况（它们互不相交）：

考虑 Bob 必胜的情况，不难发现，当且仅当这 2n 个数全部可以找到另一个数，使得它们之间满足以上三种条件之一，则 Bob 必胜；否则 Alice 必胜。因此，我们把以上三个条件推广到所有数。

后两个条件可以合并，即对于一个数对 $\left(a,b\right)$，不妨设 $a<b$，则 $\left(a+\frac m2\right)\bmod m=b$ 且 $m$ 为偶数。 只看剩余的两两不同的数： - 如果不存在剩余的数，那么 Bob 必胜。 - 如果 $m$ 为奇数，那么必然不满足条件，此时 Alice 必胜。 - 如果存在一个数 $a$ 且不存在一个数 $\left(a+\frac m2\right)\bmod m$，那么必然不满足条件，此时 Alice 必胜。 特判完以上情况，仍然不能保证 Bob 必胜，因为每选一对数 $a,\left(a+\frac m2\right)\bmod m$，都会使 Alice 与 Bob 删除的数之和 $x,y$ 的差增加 $\frac m2$。因此，当且仅当数对 $a,\left(a+\frac m2\right)\bmod m$ 的个数为偶数时，$x,y$ 的差模 $m$ 才会为 $0$，即 $x\equiv y\pmod m$，此时 Bob 必胜；否则，最终 $x,y$ 的差必然是 $\frac m2$，此时 Alice 必胜。 然后就是代码了： ```c++ int n,m; set<int> s; int main() { n=read(),m=read(); for(int i=1;i<=(n<<1);i++) { int num=read(); if(s.find(num)==s.end()) s.insert(num); else s.erase(num); // 抵消掉相同的数 } if(s.empty()) puts("Bob"); else { // 此时剩余两两不同的数 if(m&1) puts("Alice"); else { // 此时m为偶数 int cnt=0; for(auto num:s) { if(s.find((num+(m>>1))%m)==s.end()) { puts("Alice"); return 0; } cnt++; } // 此时cnt表示满足条件的数的个数，除以2才是数对的个数 cnt>>=1; if(cnt&1) puts("Alice"); else puts("Bob"); } } return 0; } ```