巴什博奕（Bash Game）
$A$和$B$一块报数，每人每次报最少1个，最多报4个，看谁先报到30。
在第一次报数时，假设$A$报$k$个数，那么$B$就报$5-k$个数。$B$报数之后问题就变为：$A$和$B$一块报数，看谁先报到$25$。
进而变为看谁先报到$20$、$15$、$10$、$5$，当报到还剩$5$个数字的时候，不管$A$怎么报数，最后一个数肯定是$B$报的，因为$A$不可能一次报完5个数。
可以看出，作为后手的$B$在这个游戏中是不会输的。
把结论拓广：
如果我们要报$n$个数，每次最少报一个，最多报$m$个
我们可以找到这么一个整数$k$和$r$，使$n=k*（m+1）+r$
如果$r=0$，那么先手必败；否则先手必胜
反巴什博弈
在普通的巴什博弈中，如果我们规定最后报数者输，那么又如何考虑呢？
如果先手第一步报了$n - 1$个数字，此时剩下$1$个数字给后手，后手必败（因为这$1$个数字必报，报了他就是最后一个报数的人）。
那么这个问题就转换为：有一堆$n – 1$个物品，最后取光者胜。
此时操作方式和基础巴什博弈一样，永远跟对方凑$m + 1$即可。
结论：$(n - 1) \% (m + 1)=0$时，后手胜，反之先手胜。
威佐夫博弈（Wythoff Game）
有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
直接说结论了：
若两堆物品的初始值为$x$、$y$，且$x<y$，则令：$z=y-x$
记$w=(int)[((\sqrt5+1)/2)*z]$
若$w=x$，则先手必败，否则先手必胜。
尼姆博弈（Nimm Game）
有任意堆物品，每堆物品的个数是任意的，双方轮流从堆中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
结论就是：
把每堆物品数全部异或起来，如果得到的值为$0$，那么先手必败，否则先手必胜。
斐波那契博弈
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能一次把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
结论是：
先手胜当且仅当$n$不是斐波那契数（$n$为物品总数）
反尼姆博弈
有$n$堆石子,两个人轮流从某一堆中任意取走一定量的石子,最后不能取的为赢家
注意：
- 每次只能从一堆取任意个，可以取完这堆，但不能不取
- 取最后一个石子的为输家
这种博弈被称为反$Nim$博弈，只要满足以下两种情况之一先手就必胜：
- 各堆石子数目异或结果不为$0$，且至少有一堆石子数目大于$1$
- 各堆石子数目异或结果为$0$，且每一堆石子数目均为$1$
取石子后还可以移动石子
共有$N$堆石子，已知每堆中石子的数量。
两个人轮流取子，每次只能选择$N$堆石子中的一堆，取一定数量的石子（最少取一个）。
但是取过石子之后，还可以将该堆石子中剩下的任意多个石子中随意选取几个放到其它的任意一堆或几堆上。
等哪个人无法取子时就表示此人输掉了游戏。
注意：一堆石子没有子之后，就不能再往此处放石子了。
结论：$N$为偶数，且相同石子数的石子堆的堆数也为偶数时为必败态，其余均为必胜态。
例如：有$4$堆石子，每堆石子的个数分别为：$6$、$6$、$8$、$8$，这种情况就是必败态。
SG函数
首先定义一种$mex(minimal \ excludant)$运算：
一种施加于一个集合的运算，表示最小的不属于这个集合的非负整数。
例如：$mex{0,1,2,4}=3$、$mex{2,3,5}=0$、$mex{}=0$。
对于任意状态$x$，定义$SG(x) = mex(F)$，其中$F$是$x$的后继状态的$SG$函数值的集合。
$SG$函数返回值为$0$代表$x$为必败点，否则为必胜点。
一个模板：
void gao(int n)
{
memset(sg,0,sizeof(sg));
for(int i=1;i<=n;++i)//注意要从小到大枚举
{
memset(vis,0,sizeof(vis));
for(int j=0;j<=min(i,k);++j)
{
if(i==j) continue;
int tmp=i-j-v[i-j];//tmp是能抵达的子局面
if(tmp>=0)
vis[sg[tmp]]=1;
}
for(int j=0;;j++)
if(!vis[j])
{
sg[i]=j;
break;
}
}
}
注意有多堆的时候，可以单独把每一堆求出$SG$函数值，然后算出异或和，为$0$则先手必败：
for(int i=1,n;i<=p;++i)
{
scanf("%d",&n);
for(int j=1;j<=n;++j)
scanf("%d",&v[j]);
gao(n);
ans^=sg[n];
}