场上 个整数, Alice,Bob 轮流取数, Alice 先手,如果最终 Alice 取出数的和取模 和 Bob 取出来数的和相等,那么 Bob 获胜,否则 Alice 获胜。
两个人绝对聪明,求哪个人会获胜。
考虑最后剩下两个数 且的情况,显然此时 Alice
先手。设此时两人的数的和分别为 和 ,那么 Bob
胜当且仅当 且 ,两式相加减可以把条件转化为 且 且 且 。观察到只有以下几种情况满足条件:
- 且 ;
- 为偶数且 且 ;
那么不难发现若能把 分成若干组 和偶数组 ( 是偶数时)则 Bob
必胜,因为可以取和 Alice
取的那个数组成一组的那个数。
考虑证明这个条件是充要的,即证明其他情况 Alice
必胜。其实很好证明,只要让 Alice
模仿 Bob
操作,Bob
取能组成一组的她就取这一组中的另一个,Bob
取零散的 Alice
也取零散的,这样最后剩下的两个数字一定不能组成一组,并且零散的数字互相组成 来消掉的情况 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;
}