友好的新人题解

首先我们要先知道Nim游戏的输赢怎么判断的，先说结论：当每一堆石子数的Nim和（即异或和）为0的时候先手必败，反之先手必胜，下面我们来准备证明一下，但我们的证明围绕了一个好东西：

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

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

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

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

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

好了，开始做这个题了：

首先如果初始的Nim和就是0，那先手一定必败。

然后如果初始的Nim和不为0，那么先手一定可以找到一堆石子拿走若干石子后让Nim和变为0，因为至少最大的那一堆满足，但其它堆能否满足我们不知道，现在让我们想想如何判断一堆石子是否可以让先手取走其中的部分石子后让Nim和变为0，假设这一堆石子的数量为 $a$，玩家取走了 $b$ 个，其它堆的异或和为 $p$，那么有一下推理：

首先如果这个堆可能能让先手取走一些石子后Nim和变为0，那么一定存在一个 $b$ 使得 $(a-b)\oplus p=0$，其中 $\oplus$ 表示异或，根据两个相同的数异或才为0，我们得到 $a-b=p$ 也就是说 $a>p$，好了，问题解决，看看核心代码吧

n=iread();
FOR(i,1,n) a[i]=iread();
int sum=0;
FOR(i,1,n) sum^=a[i];
if(!sum) puts("0");
else {
   	int cnt=0;	
   	FOR(i,1,n){
   		sum^=a[i];
   		if(a[i]>sum) ++cnt;
   		sum^=a[i];
   	}
   	cout<<cnt<<endl;
}