【题目来源】
http://acm.hdu.edu.cn/showproblem.php?pid=1850

【题目描述】
下面是一个二人小游戏：桌子上有 M 堆扑克牌，每堆牌的数量分别为 Ni（i=1…M）。两人轮流进行。每走一步可以任意选择一堆并取走其中的任意张牌。桌子上的扑克全部取光，则游戏结束。最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负，我只想问大家：
——“先手的人如果想赢，第一步有几种选择呢？”

【输入格式】
输入数据包含多个测试用例，每个测试用例占 2 行，首先一行包含一个整数 M（1<M<=100），表示扑克牌的堆数，紧接着一行包含 M 个整数 Ni（1<=Ni<=1000000，i=1…M），分别表示 M 堆扑克的数量。M 为 0 则表示输入数据的结束。

【输出格式】
如果先手的人能赢，请输出他第一步可行的方案数，否则请输出 0，每个实例的输出占一行。

【输入样例】
3
5 7 9
0

【输出样例】
1

【数据范围】
1<M<=100，
1<=Ni<=1000000，i=1…M

【算法分析】
● 经典 Nim 博弈定理：对于任意的 {a1, a2, a3, …, an}，若 S=a1⊕a2⊕a3⊕⋯⊕an 的值不等于 0，先手必胜，记为 N-position（先手必胜态）。若 S=a1⊕a2⊕a3⊕⋯⊕an 的值等于 0，先手必败，记为 P-position（先手必败态）。

● 根据经典 Nim 博弈定理，若要让对手进入必败态（P-position），需通过一步操作将总异或和 S=a1⊕a2⊕a3⊕⋯⊕an 变为 0。即若设对第 i 堆石子操作后，其数量 ai 变为 t，则此时对手进入必败态的条件为：a1​⊕a2​⊕⋯⊕t⊕⋯⊕an​=0。
由于异或满足交换律 / 结合律，故可将上式变形，得：(a1⊕a2⊕⋯⊕ai⊕⋯⊕an)⊕ai⊕t=0，代入 S=a1⊕a2⊕⋯⊕an，得 S⊕ai⊕t=0。
由于异或满足性质（x⊕x=0 及 0⊕x=x），故可由 S⊕ai⊕t=0 推得 t=S⊕ai。
Nim 游戏的合法操作是从第 i 堆拿走若干石子（至少 1 个），即操作后第 i 堆石子数 t 需满足 0≤t<ai。​结合上文结论 t=S⊕ai，可得“先手必胜”的充要条件为：S⊕ai<ai。

● 异或运算的基本性质（https://blog.csdn.net/hnjzsyjyj/article/details/154304346）
异或运算（XOR）具有以下重要性质：
交换律‌：a ^ b = b ^ a
结合律‌：a ^ (b ^ c) = (a ^ b) ^ c
自反性‌：a ^ a = 0
零元素‌：a ^ 0 = a
可逆性‌：如果 a ^ b = c，那么 a = c ^ b

【算法代码】
切记：HDU OJ 不支持万能头文件。

#include <iostream>
using namespace std;

const int N=1e2+5;
int a[N];

int main() {
    int n;
    while(cin>>n) {
        if(n==0) break;
        int t=0,cnt=0;
        for(int i=1; i<=n; i++) {
            cin>>a[i];
            t^=a[i];
        }

        for(int i=1; i<=n; i++) {
            if((t^a[i])<a[i]) cnt++;
        }
        cout<<cnt<<endl;
    }

    return 0;
}

/*
in:
3
5 7 9
0

out:
1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/158728832
https://www.acwing.com/solution/content/13187/
https://blog.csdn.net/hnjzsyjyj/article/details/154304346
https://www.acwing.com/file_system/file/content/whole/index/content/12084580/
https://blog.csdn.net/hnjzsyjyj/article/details/158704426
https://blog.csdn.net/hnjzsyjyj/article/details/154310120