参考博客：https://www.cnblogs.com/csushl/p/9943000.html
有详细证明

Nim

nim结论：对于一个局面，当且仅当a[1] xor a[2] xor ...xor a[n]=0时，该局面为P局面，即必败局面。(对于取任意个数SG(x)=x,也符合SG定理).

• 结论变换：把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(2)全部为0，则必败，否则必胜。

anti-nim(反nim游戏)

题目链接:https://ac.nowcoder.com/acm/problem/20410

正常的nim游戏是取走最后一颗的人获胜，而反nim游戏是取走最后一颗的人输。
一个状态为必胜态，当且仅当：

• 1）所有堆的石子个数为1，且NIM_sum(xor)=0
• 2）至少有一堆的石子个数大于1，且 NIM_sum(xor)≠0

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;

int main()
{
    int n,m;
    scanf("%d",&m);
    for( int i=1;i<=m;i++ )
    {
        scanf("%d",&n);
        int ans=0;
        int flag=0;
        for( int j=1;j<=n;j++ )
        {
            int x;scanf("%d",&x);
            if( x>1 ) flag=1;
            ans^=x;
        }
        if( !flag && !ans ) puts("John");
        else if( flag && ans ) puts("John");
        else puts("Brother");
    }
}

Moore’s Nim：

题目链接:https://acm.sdut.edu.cn/onlinejudge3/problems/2161

模型：n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败。

这是一个nim游戏的变形，也是有结论：把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜。

n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败。

这是一个nim游戏的变形，也是有结论：

• 把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜。
• 该结论可以类比普通的Nim博弈(理解)，Nim博弈每次对一堆操作，那么判断每一位二进制位个数是否mod(2)全为0。

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;
int a[32];

int main()
{
    int t;scanf("%d",&t);
    while( t-- )
    {
        int n;scanf("%d",&n);
        for( int i=0;i<30;i++ ) a[i]=0;
        for( int i=1;i<=n;i++ )
        {
            int x;scanf("%d",&x);
            int cnt=0;
            while( x )
            {
                if( x&1 ) a[cnt]++;
                cnt++;
                x>>=1;
            }
        } 
        bool flag=true;
        for( int i=0;i<30;i++ ) if( a[i]%4 ) flag=false;
        if( !flag ) puts("Yes");
        else puts("No"); 
    }
}

Mis`ere Moore’s Nimk

其他的条件一样，只是谁拿走最后一个谁输。
先手必胜:

• 1.石子规模都为1，且堆数mod (m + 1) != 1
• 2.石子规模不全为1，且当堆数以2进制表示时，存在某一二进制位上1的和mod(m + 1) != 0

鸽~

Staircase NIM

题目链接：http://poj.org/problem?id=1704

顾名思义就是在阶梯上进行，有若干个石子放在阶梯上，每次可以选择任意层的任意个石子将其移动到该层的下一层。最后不能操作的人输。
解法: 对奇数堆进行Nim博弈，因为我们根据必胜策略将奇数堆的石子移动到偶数堆(类比于从一堆中拿走任意石子)，如果对手将该堆石子移动的下一个奇数堆，我们只需要将这堆石子继续移动到偶数堆。如果对手操作其他奇数堆的石子，那么就是奇数堆石子的Nim博弈。

该题石子数的转化是两堆石子的位置差值。

• 对与相近的两个棋子，将其看做石子数为2个棋子之间的空隙的石子堆。设想当前是必胜态，如果对手移动右棋子，那和取石子无异，如果是移动左棋子呢？我们可以相应地移动右棋子，使空隙数不变，这样仍然回到了必胜的状态。

#include<iostream>
#include<cstdio>
#include<algorithm> 
using namespace std;

const int maxn=2e5+10;
int m,n;
int a[maxn];

int main()
{
    scanf("%d",&m);
    for( int i=1;i<=m;i++ )
    {
        scanf("%d",&n);
        int ans=0;
        for( int j=1;j<=n;j++ ) scanf("%d",&a[j]);
        if( n&1 ) a[++n]=0;
        sort(a+1,a+1+n);

        for( int i=2;i<=n;i+=2 )
        {
            ans^=a[i]-a[i-1]-1;
        }
        if( ans ) puts("Georgia will win");
        else puts("Bob will win");
    }
} 

HDU1730

http://acm.hdu.edu.cn/showproblem.php?pid=1730

题意：如图所示，游戏在一个n行m列的棋盘上进行，每行有一个黑子（黑方）和一个白子（白方）。执黑的一方先行，每次玩家可以移动己方的任何一枚棋子到同一行的任何一个空格上，当然这过程中不许越过该行的敌方棋子。双方轮流移动，直到某一方无法行动为止，移动最后一步的玩家获胜。

分析：每一行中加的距离可以看作是石子的堆数，因为每一个当一个人往两侧走的时候，另一个人可以往那个方向走直至距离一样，这个基础上它还可以再走，所以中间的距离只会减少不会增加，就可以看作是一个多堆石子的Nim游戏。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>

using namespace std;

const int maxn=4e3+10;


int main()
{
    int n,m;
    while( cin>>n>>m )
    {
        int a,b,ans=0;
        while( n-- )
        {
            cin>>a>>b;
            ans^=(abs(a-b)-1);
        }
        if( ans ) puts("I WIN!");
        else puts("BAD LUCK!");
    }
}

新Nim游戏:

在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。
解法：
为使后手必败，先手留给后手的必然是若干线性无关的数字，否则后手可以留下一个异或和为零的非空子集使得先手必败，故问题转化为拿走和最小的数字使得留下的数线性无关，即留下和最大的线性基，这样拿走的数量显然最少，找到和最大的线性基只需贪心的把数字从大到小加入到基中即可（证明需用到拟阵）
抱歉只会cv结论

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum;
int k,num[520],d[520];
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int Insert(int k)
{
    for(int i=31;i>=0;--i)
    {
        if(k&(1<<i))
        {
            if(!d[i]) {d[i]=k; return 1;}
            else k^=d[i];
        }
    }
    return 0;
}
bool cmp(int a,int b) {return a>b;}

int main()
{
    k=read();sum=0;
    for(int i=1;i<=k;++i) num[i]=read();
    sort(num+1,num+1+k,cmp);
    for(int i=1;i<=k;++i) if(!Insert(num[i])) sum+=num[i]*1ll;
    printf("%lld\n",sum);
    return 0;
}