尼姆游戏（Nim Game)入门

巴什游戏只有一堆石头，尼姆游戏将堆数扩展到n堆

规则是：

有n堆石子，数量分别是:{a1,a2,a3,....,an}，两个玩家轮流拿石子，每次可以在任意一堆中拿走任意数量的石子，拿到最后一个石子的玩家获胜

有一个极其简单的方法来判断胜负：

若(a[1]^a[2]^a[3]^....^a[n)==0，那么先手必败，否则必胜

证明：

1.必定能从N状态转化到P状态。也就是说，先手处于必胜点，可以拿走一些石子，让后者必败。具体方法是：任选一堆，例如第i堆，石头数量是k，让剩下n-1堆做异或运算，设结果为H，如果H比k小，就把第i堆石头减少到H，这样操作之后，因为H^H=0，所以n堆石头异或等于0

2.进入P状态后，轮到的下一个玩家，不管拿多少石子都会转移到N状态。因为任何一堆的变化，都会使这堆石子至少一个二进制位发生变化，导致异或运算的结果不等于0

3.在游戏过程中，按上述过程在N状态和P状态之间交替转化，直到所有堆石头都是0，即终止于P状态。

例题：Problem - 1850 (hdu.edu.cn)

题意：

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

分析：

枚举必胜点的位置即可

必胜点是指在可以这个点取走一些石子使得剩下的n-1堆石子堆异或的结果等于这个堆，即剩下n-1堆石子堆异或的结果小于这个堆。

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e2+10;
int n,sum,ans;
int a[mxn];
void solve(){
    while(cin>>n&&n!=0){
        ans=0;sum=0;
        for(int i=1;i<=n;i++) cin>>a[i],sum^=a[i];
        if(sum==0) puts("0");
        else{
            for(int i=1;i<=n;i++){
                if((sum^a[i])<a[i]) ans++;
            }
            printf("%d\n",ans);
        }
    }
}
int main(){
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}