前往：我自己搭建的博客
题目
洛谷P2197nim游戏
题解
假设第i堆石子有ai个。
当所有物品都被取完后，x=0，对手取走最后一个，我方失败。
若x!=0,设x的二进制表示下的最高位的1在第k位，那么至少存在一个ai，它的第k位为1,。显然，对ai有一种取法，使得x=0。
若x=0,任意一种取法都会导致x!=0。
综上，由数学归纳法得：x!=0先手必胜，因为永远可以让对手面对x=0的局面；x=0先手必败，因为永远可以让对手面对x!=0的必胜局面。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
inline bool nim()
{
int ans=0,tmp;
for(int i=1;i<=n;i++) scanf("%d",&tmp),ans^=tmp;
if(ans) return 1;
else return 0;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
if(nim()) printf("Yes\n");
else printf("No\n");
}
return 0;
}
