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游戏。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月20日 星期三 19时47分48秒
4File Name :code/hdu/1850.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=105;
32const int M=1E6+7;
1int n;
2int sg[M];
3int a[N];
4void sg_init()
5{
6 //这个可以记成结论23333
7 for ( int i = 1 ; i < M ; i ++) sg[i] = i ;
8}
9int main()
10{
11 #ifndef ONLINE_JUDGE
12 freopen("code/in.txt","r",stdin);
13 #endif
14 sg_init();
15 while (~scanf("%d",&n))
16 {
17 if (n==0) break;
18 int sum = 0 ;
19 for ( int i = 1 ; i <= n ; i++)
20 {
21 int x;
22 scanf("%d",&x);
23 a[i] = x;
24 sum^=sg[x];
25 }
26 if (sum==0)
27 {
28 puts("0");
29 continue;
30 }
31 int ans = 0 ;
32 for ( int i = 1 ; i <= n ; i++)
33 if ((a[i]^sum)<a[i]) ans++;
34 printf("%d\n",ans);
35 }
36 #ifndef ONLINE_JUDGE
37 fclose(stdin);
38 #endif
39 return 0;
40}