AT_arc148_d [ARC148D] mod M Game 做题记录

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

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

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 2M1092 \leq M \leq 10^9
  • 0AiM10 \leq A_i \leq M - 1

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

  • xy(modM)x\equiv y\pmod Mab(modM)a\equiv b\pmod M
  • MM 为偶数且 x+M2y(modM)x+\frac{M}{2}\equiv y\pmod Ma+M2b(modM)a+\frac{M}{2}\equiv b\pmod M

那么不难发现若能把 AiA_i 分成若干组 xy(modM)x\equiv y\pmod M偶数x+M2y(modM)x+\frac{M}{2}\equiv y\pmod MMM 是偶数时)则 Bob 必胜,因为可以取和 Alice 取的那个数组成一组的那个数。

考虑证明这个条件是充要的,即证明其他情况 Alice 必胜。其实很好证明,只要让 Alice 模仿 Bob 操作,Bob 取能组成一组的她就取这一组中的另一个,Bob 取零散的 Alice 也取零散的,这样最后剩下的两个数字一定不能组成一组,并且零散的数字互相组成 MM 来消掉的情况 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;
}