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;
33
34int n;
35int sg[M];
36int a[N];
37void sg_init()
38{
39 //这个可以记成结论23333
40 for ( int i = 1 ; i < M ; i ++) sg[i] = i ;
41}
42int main()
43{
44 #ifndef ONLINE_JUDGE
45 freopen("code/in.txt","r",stdin);
46 #endif
47 sg_init();
48 while (~scanf("%d",&n))
49 {
50 if (n==0) break;
51 int sum = 0 ;
52 for ( int i = 1 ; i <= n ; i++)
53 {
54 int x;
55 scanf("%d",&x);
56 a[i] = x;
57 sum^=sg[x];
58 }
59 if (sum==0)
60 {
61 puts("0");
62 continue;
63 }
64 int ans = 0 ;
65 for ( int i = 1 ; i <= n ; i++)
66 if ((a[i]^sum)<a[i]) ans++;
67 printf("%d\n",ans);
68 }
69 #ifndef ONLINE_JUDGE
70 fclose(stdin);
71 #endif
72 return 0;
73}