关键词：
经典NIM游戏：
一共有N堆石子，编号1..n，第i堆中有个a[i]个石子。
每一次操作Alice和Bob可以从任意一堆石子中取出任意数量的石子，至少取一颗，至多取出这一堆剩下的所有石子。
两个人轮流行动，取走最后一个的人胜利。Alice为先手。
我们定义：
P：表示当前局面下先手必败
N：表示当前局面下先手必胜
N，P状态的转移满足如下性质：
1.合法操作集合为空的局面为P
2.可以移动到P的局面为N，这个很好理解，以为只要能转换到P局面，那么先手只需要使操作后变成P局面，那么后手就面临了一个必败的状态。
3.所有移动只能到达N的局面为P。无论怎么选取都会留给对手一个必胜状态。
其实知道这个之后应该是可以记忆化搜索或者用sg函数求解的，但是如果范围非常大，就没法做了。
就引进了nim游戏一个很神奇的结论：对于一个局面，当且仅当a[1] xor a[2] xor ...xor a[n]=0时，该局面为P局面，即必败局面。
证明如下：
1.全0的局面一定是P局面。
2.从任意一个异或值不为0（设为K）的局面一定可以转移到一个异或值为0的状态。由于异或计算的特殊性，我们知道一定有一个a[i]的某一位与k的最高位的1是相同的，那么必然有a[i] xor k<a[i],我们可以通过改变a[i[的值为a[i]‘，使a[1] xor a[2] xor a[i] xor ...xor a[n]=0
3.对于任意一个局面，若异或值为0，则不存在任何一个移动可以使新的局面的异或值为0.如果一位的异或值为0，那么这一位上一定有偶数个1，那么只改变一个数，一定无法使其保持0
Moore’s Nim：
n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败。
这是一个nim游戏的变形，也是有结论：把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜。
证明如下：
1.全为0的局面一定是必败态。
2.任何一个P状态，经过一次操作以后必然会到达N状态：在某一次移动中，至少有一堆被改变，也就是说至少有一个二进制位被改变。由于最多只能改变k堆石子，所以对于任何一个二进制位，1的个数至多改变k。而由于原先的总数为k+1的整数倍，所以改变之后必然不可能是k+1的整数倍。故在P状态下一次操作的结果必然是N状态。
3.任何N状态，总有一种操作使其变化成P状态。从高位到低位考虑所有的二进制位。假设用了某种方法，改变了m堆，使i为之前的所有位都回归到k+1的整数倍。现在要证明总有一种方法让第i位也恢复到k+1的整数倍。
有一个比较显然的性质，对于那些已经改变的m堆，当前位可以自由选择1或0.
设除去已经更改的m堆，剩下堆i位上1的总和为sum
分类讨论：
(1)sum<=k-m,此时可以将这些堆上的1全部拿掉，然后让那m堆得i位全部置成0.
(2)sum>k-m 此时我们在之前改变的m堆中选择k+1-sum堆，将他们的第i位设置成1。剩下的设置成0.由于k+1-sum<k+1-(k-m)<m+1,也就是说k+1-sum<=m，故这是可以达到的；
anti-nim反nim游戏：
正常的nim游戏是取走最后一颗的人获胜，而反nim游戏是取走最后一颗的人输。
一个状态为必胜态，当且仅当：
1）所有堆的石子个数为1，且NIM_sum(xor和)=0
2）至少有一堆的石子个数大于1，且 NIM_sum(xor和)≠0
题目：bzoj 1022: [SHOI2008]小约翰的游戏John
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
scanf("%d",&m);
for (int j=1;j<=m;j++)
scanf("%d",&n);
int ans=0; int pd=0;
for (int i=1;i<=n;i++)
int x; scanf("%d",&x);
if (x>1) pd=1;
ans^=x;
if (pd==0&&!ans) printf("John
");
else if (pd==1&&ans) printf("John
");
else printf("Brother
");
Staircase NIM
顾名思义就是在阶梯上进行，每层有若干个石子，每次可以选择任意层的任意个石子将其移动到该层的下一层。最后不能操作的人输。
阶梯博弈经过转换可以变为Nim..把所有奇数阶梯看成N堆石子做nim。把石子从奇数堆移动到偶数堆可以理解为拿走石子，就相当于几个奇数堆的石子在做Nim。
假设我们是先手，所给的阶梯石子状态的奇数堆做Nim先手能必胜.我就按照能赢的步骤将奇数堆的石子移动到偶数堆.如果对手也是移动奇数堆，我们继续移动奇数堆.如果对手将偶数堆的石子移动到了奇数堆..那么我们紧接着将对手所移动的这么多石子从那个奇数堆移动到下面的偶数堆.两次操作后.相当于偶数堆的石子向下移动了几个。而奇数堆依然是原来的样子，即为必胜的状态。就算后手一直在移动偶数堆的石子到奇数堆，我们就一直跟着他将石子继续往下移，保持奇数堆不变。我可以跟着后手把偶数堆的石子最终移动到0，然后对手就不能移动这些石子了.所以整个过程.将偶数堆移动到奇数堆不会影响奇数堆做Nim博弈的过程..整个过程可以抽象为奇数堆的Nim博弈.
为什么是只对奇数堆做Nim就可以而不是偶数堆呢？因为如果是对偶数堆做Nim，对手移动奇数堆的石子到偶数堆，我们跟着移动这些石子到下一个奇数堆。那么最后是对手把这些石子移动到了0，我们不能继续跟着移动，就只能去破坏原有的Nim而导致胜负关系的不确定。所以只要对奇数堆做Nim判断即可知道胜负情况。
题目：http://poj.org/problem?id=1704
#include<bits/stdc++.h>
using namespace std;
int m,n;
int a[N],p[N],b[N];
int main()
freopen("a.in","r",stdin);
scanf("%d",&m);
for (int i=1;i<=m;i++)
scanf("%d",&n); int ans=0;
int cnt=0;
for (int j=1;j<=n;j++) scanf("%d",&a[j]);
sort(a+1,a+n+1);
for (int j=2;j<=n;j++) p[j]=a[j]-a[j-1]-1;
p[1]=a[1]-1;
for (int j=1;j<=n;j++) b[j]=p[n-j+1];
for (int j=1;j<=n;j++)
if (!b[j]) cnt++;
if (j&1) ans^=b[j];
if (cnt==n)
printf("Bob will win
");
continue;
if (ans) printf("Georgia will win
");
else printf("Bob will win
");
return 0;
新Nim游戏:
为使后手必败，先手留给后手的必然是若干线性无关的数字，否则后手可以留下一个异或和为零的非空子集使得先手必败，故问题转化为拿走和最小的数字使得留下的数线性无关，即留下和最大的线性基，这样拿走的数量显然最少，找到和最大的线性基只需贪心的把数字从大到小加入到基中即可（证明需用到拟阵）
例题：BZOJ3105
#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
",sum);
return 0;
威佐夫博弈:
两堆石子，每次可以取一堆或两堆，从两堆中取得时候个数必须相同，先取完的获胜。
这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示
两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们
称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，
10）、（8，13）、（9，15）、（11，18）、（12，20）。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有
如下三条性质：
1。任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak
-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2。任意操作都可将奇异局势变为非奇异局势。
事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其
他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由
于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3。采用适当的方法，可以将非奇异局势变为奇异局势。
假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了
奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b – bk个物体，即变为奇异局
势；如果 a = ak ， b < bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局
势（ ab – ak , ab – ak+ b – ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余
的数量a – ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）
,从第二堆里面拿走 b – bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b – a
j 即可。
从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜
；反之，则后拿者取胜。
那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)
题目：http://poj.org/problem?id=1067
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
double k=(1+sqrt(5.0))/2;
while(scanf("%d%d",&n,&m)!=EOF)
if (n>m) swap(n,m);
int t=m-n;
if (n==(int)((double)t*k)) printf("0
");
else printf("1
");
return 0;
巴什博奕
只有一堆石子共n个。每次从最少取1个，最多取m个，最后取光的人取胜。
问先手是否有必胜策略，第一步该怎么取。
如果n=(m+1)*k+s (s!=0) 那么先手一定必胜，因为第一次取走s个，接下来无论对手怎么取，我们都能保证取到所有(m+1)倍数的点，那么循环下去一定能取到最后一个。
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1846
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
int t;
scanf("%d",&t);
for (int i=1;i<=t;i++)
scanf("%d%d",&n,&m);
if (n%(m+1)) printf("first
");
else printf("second
");
return 0;
博弈论入门之威佐夫博弈(代码片段)
...一类经典的博弈问题有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取得人输，分析谁会获得胜利博弈分析威佐夫博弈不同于Nim游戏与巴什博... 查看详情
博弈论（巴什博奕，威佐夫博弈，尼姆博弈，斐波那契博弈）
一、巴什博弈（BashGame）有n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩... 查看详情
博弈论（巴什博奕，威佐夫博弈，尼姆博弈，斐波那契博弈）
...，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就... 查看详情
巴仕博弈+威佐夫博弈(代码片段)
...理说应该是不在话下了巴什博奕：两个顶尖聪明的人在玩游戏，有n个石子，每人可以随便拿1到m个石子，不能拿的人为败者，问谁会胜利巴什博奕是博弈论问题中基础的问题它是最简单的一种情形对应一种状态的博弈博弈分析如... 查看详情
acm第十二天(代码片段)
...报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就变为，A和B一块报数，... 查看详情
博弈论——两人取子游戏与威佐夫博弈，隐藏在背后的黄金分割(代码片段)
本文始发于个人公众号：TechFlow，原创不易，求个关注今天是算法和数据结构专题第25篇文章，我们继续博弈论专题。在上一篇文章当中我们了解了最简单的巴什博奕，今天我们来看看另一个经典的博弈模型——威佐夫博弈。博... 查看详情
博弈论（取石子游戏）
参考题集就好了http://url.cn/5qNJibq基本博弈1，巴什博奕（BashGame）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。必胜条件： n=（m+1）r+s2，威佐夫博弈（WythoffGame）：... 查看详情
一些博弈
...报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数 查看详情
nyoj1077小博弈另类巴什博奕
分析：分析当整除（a+b）的时候肯定是后者胜利，假设余数不等于0的时候。假设余数大于b肯定是前者胜利，否则后者胜利。代码：importjava.math.*;importjava.util.Scanner;publicclassMain{ publicstaticvoidmain(String[]args){ Scannercin=newScanner(System.in... 查看详情
博弈基础
...报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就变为，A和B一块报数，... 查看详情
nyoj1077小博弈另类巴什博奕
分析：分析当整除（a+b）的时候肯定是后者胜利，假设余数不等于0的时候，假设余数大于b肯定是前者胜利。否则后者胜利。代码：importjava.math.*;importjava.util.Scanner;publicclassMain{ publicstaticvoidmain(String[]args){ Scannercin=newScanner(Syste... 查看详情
小小的学习一发博弈
...报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就变为，A和B一块报数，... 查看详情
博弈问题（巴什博弈威佐夫博弈尼姆博弈斐波拉契博弈）结论
巴什博弈有一堆n个石子从里面取，一次从里面取1~m个，最后取完者获胜。结论：如果n%（m+1）==0先手必败 n%（m+1）！=0为先手必胜。HDU4764#include<iostream>#include<algorithm>usingnamespacestd;intmain() intn,m; while(cin>>n>>m) 查看详情
51nod1185威佐夫游戏v2(威佐夫博弈)
1185 威佐夫游戏 V2 基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注有2堆石子。AB两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不... 查看详情
博弈专题
HDU1846BraveGame 巴什博奕简单版。常见四种博弈的讲解：https://blog.csdn.net/ac_gibson/article/details/41624623HDU2897邂逅明下巴什博奕复杂版。（巴什博奕注意的2个地方，第一：不管第一个人拿几个，第二个人一定可以使两个人 ... 查看详情
博弈论(基础概念+例题)
博弈论(b站视频)文章目录一些概念以Nim游戏为例Nim游戏介绍定义必败/必胜局面必败/必胜局面的判定引理Nim游戏判定引理的等价命题有向图游戏对判定引理的数学描述-Sg函数有向图游戏的和题目：[有向图游戏][有向图游戏的... 查看详情
292.nim游戏博弈论(代码片段)
https://leetcode-cn.com/problems/nim-game/如果是4的倍数无论如何拿都是必输。classSolutionpublic:boolcanWinNim(intn)if(n%4)returntrue;returnfalse;; 查看详情
hdu1527取石子游戏(威佐夫博弈)
TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8509 AcceptedSubmission(s):4833ProblemDescription有两堆石子，数量任意，可以不 查看详情