HDU_1850
这个相当于有M个子游戏，每个子游戏的SG函数简略写一下之后也比较容易搞出来，最后会发现sg[i][Ni]=Ni，那么如果所有的sg[i][Ni]异或以后的结果为0，是必然会输的。
接着我们考虑先手必赢的情况，如果从一堆中拿走一些石子后，能使得sg异或值为0的话，就算有一种方案，同时根据x^x=0的原理，对于第i个石堆，我们可以先将其余石堆的sg函数的异或值算出来，这样就得到了第i个石堆需要变成多少个石头才能必赢，如果要变成的这个数量比石堆原有的石子数量小的话，就说明存在一种方案。
上面的做法是O(n^2)，原因在于我们每次都算了一遍其余sg函数的异或值，但实际上是是没有必要的。根据x^x=0和x^0=x，我们可以先将所有sg函数的异或值算出来，每次将这个值异或Ni就可以得到除了第i堆之外的所有sg函数的异或值，这样就可以做到O(1)的时间计算出其余sg函数的异或值，整体是O(n)的复杂度。
另外推荐一个讲SG函数入门知识的博客：http://www.cnblogs.com/Knuth/archive/2009/09/05/1561007.html。
#include<stdio.h>
#include<string.h>
#define MAXD 1010
int M, n[MAXD];
void solve()
{
int i, j, k = 0, cnt = 0;
for(i = 0; i < M; i ++)
{
scanf("%d", &n[i]);
k ^= n[i];
}
for(i = 0; i < M; i ++)
{
if((k ^ n[i]) < n[i])
++ cnt;
}
printf("%d\n", cnt);
}
int main()
{
for(;;)
{
scanf("%d", &M);
if(!M)
break;
solve();
}
return 0;
}