带证明的题解

不知道为什么现在题解能不写证明了（

结论：当每一堆石子数的Nim和（即异或和）为0的时候先手必败，反之先手必胜，下面我们来准备证明一下，但我们的证明围绕了一个好东西：

如果一种游戏的最终局面（某一方输）满足某一性质，并且游戏中所有满足该性质的局面所能创造出的新局面都不满足该性质，同时所有不满足该性质的局面一定可以产生出至少一个满足该性质的局面，那么我们就可以根据最初局面是否满足这个性质来判断先手是否必胜。

先理解一下这个好东西的正确性：显然一个人想赢的话就需要让后手的局面满足这个性质，然后后手无论怎么创造局面到自己手里依旧不满足性质，他就可以再给后手创造一个不满足该性质的局面，久而久之后手一定会输。

回到Nim游戏里来，我们发现最终局面是没有任何石子，先手必败，满足性质Nim和为0，所有Nim和为0的局面一定只能转移到Nim和不为0的局面（我们为了行文方便，称之为性质1），所有Nim和不为0的局面只能转移到Nim和为0的局面（我们称之为性质2）。

性质1的证明：考虑反证法，如果可以找到一堆石子，然后移除部分石子让异或和不变，那意味着我们取出的这个数量在二进制下的每一位都是0，相当于我们没有取石子，所以实现不了，故性质1成立。

性质2的证明：这里可能比较难理解，我们干脆直接给出玩家该如何具体操作来证明这个性质吧，玩家先找到石子最多的一堆，然后发现这一堆的石子数一定大于其它石子堆的异或和，因为这一堆石子数量最多，所以总的异或和二进制里的最高位一定由这一堆石子数来提供，相当于说明了这一堆的石子数一定大于其它石子堆的异或和，又由于两个相同数的异或和为零，我们只需要把这一堆石子也取到其它石子堆的异或和的数量，总的异或和就为0了。

最后看代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#define ll long long
//#define int long long
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define rop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a,b) for(int i=(a);i>(b);--i)
using namespace std;
int iread(){int x=0,y=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}return x*y;}
ll lread(){ll x=0,y=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}return x*y;}
int n;
const int N=1e6+5;
int a[N];
signed main(){int T=1;while(T--){
	n=iread();
	FOR(i,1,n) a[i]=iread();
	int sum=0;
	FOR(i,1,n) sum^=a[i];
	if(!sum) puts("No");
	else puts("Yes");
}return 0;}