AT_arc148_d [ARC148D] mod M Game 做题记录

场上 $2N$ 个整数， Alice，Bob 轮流取数， Alice 先手，如果最终 Alice 取出数的和取模 $M$ 和 Bob 取出来数的和相等，那么 Bob 获胜，否则 Alice 获胜。

两个人绝对聪明，求哪个人会获胜。

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 10^9$
• $0 \leq A_i \leq M - 1$

考虑最后剩下两个数 $a,b$ 且的情况，显然此时 Alice 先手。设此时两人的数的和分别为 $x$ 和 $y$，那么 Bob 胜当且仅当 $x+a\equiv y+b\pmod M$ 且 $x+b\equiv y+a\pmod M$，两式相加减可以把条件转化为 $2x\equiv 2y\pmod M$ 且 $x-y\equiv y-x\pmod M$ 且 $2a\equiv 2b\pmod M$ 且 $a-b\equiv b-a\pmod M$。观察到只有以下几种情况满足条件：

• $x\equiv y\pmod M$ 且 $a\equiv b\pmod M$；
• $M$ 为偶数且 $x+\frac{M}{2}\equiv y\pmod M$ 且 $a+\frac{M}{2}\equiv b\pmod M$；

那么不难发现若能把 $A_i$ 分成若干组 $x\equiv y\pmod M$ 和偶数组 $x+\frac{M}{2}\equiv y\pmod M$（$M$ 是偶数时）则 Bob 必胜，因为可以取和 Alice 取的那个数组成一组的那个数。

考虑证明这个条件是充要的，即证明其他情况 Alice 必胜。其实很好证明，只要让 Alice 模仿 Bob 操作，Bob 取能组成一组的她就取这一组中的另一个，Bob 取零散的 Alice 也取零散的，这样最后剩下的两个数字一定不能组成一组，并且零散的数字互相组成 $M$ 来消掉的情况 Alice 也可以通过一些微调来避免，所以这时 Alice 必胜。

代码如下：

// Problem: [ARC148D] mod M Game
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc148_d
// Memory Limit: 1 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>

using namespace std;

const int S=400005;

int n,m,a[S];
set<int> st;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n*2;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n*2;i++)
	{
		if(st.count(a[i])) st.erase(a[i]);
		else st.insert(a[i]);
	}
	int cnt=0;
	for(int x:st)
	{
		if(m&1) return puts("Alice"),0;
		if(!st.count((x+m/2)%m)) return puts("Alice"),0;
		cnt++;
	}
	cnt/=2;
	puts((cnt&1)?"Alice":"Bob");
	return 0;
}