hdu 1850 Being a Good Boy in Spring Festival (nim游戏问必胜方案数，sg函数)

hdu1850题目链接 题意：n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。 思路：sg函数。。对于方案数，可以用nim游戏的结论。

。设异或和为sum..那么统计满足 a[i]^sum<a[i]的个数就是第一步能走的方案数。

以及。。sg函数。。如果走的步数是任意的。。也就是没有限制。。。那么sg[i] = i...此时也就退化成了一般的nim游戏。。。

/* ***********************************************
Author :111qqz
Created Time :2016年07月20日 星期三 19时47分48秒
File Name :code/hdu/1850.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=105;
const int M=1E6+7;

int n;
int sg[M];
int a[N];
void sg_init()
{
    //这个可以记成结论23333
    for ( int i = 1 ; i < M ; i ++) sg[i] = i ;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	sg_init();
	while (~scanf("%d",&n))
	{
	    if (n==0) break;
	    int sum = 0 ;
	    for ( int i = 1 ; i <= n ; i++)
	    {
		int x;
		scanf("%d",&x);
		a[i] = x;
		sum^=sg[x];
	    }
	    if (sum==0)
	    {
		puts("0");
		continue;
	    }
	    int ans = 0 ;
	    for ( int i = 1 ; i <= n ; i++)
		if ((a[i]^sum)<a[i]) ans++;
	    printf("%d\n",ans);
	}
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}