常见的博弈论有巴什博弈，威佐夫博弈，尼姆博弈，斐波那契博弈等等，今天暂时讲几个
@[toc]

一.巴什博弈

巴什博奕：只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为胜。

证明：

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。
因此我们可以推算出：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。
总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
也就是*若n%(m+1）==0，则先手必输**
变形：
如果条件不变，改成最后取光的人失败
结论：若（n-1）%（m+1）== 0 ，则后手胜利

代码

   if(n%(m+1)==0)  cout<<"后手必胜"<<endl;  
      else cout<<"先手必胜"<<endl;

二.威佐夫博奕

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
A无论怎么取，B总是可以 针对着来

结论：

奇异局势下先手必败，非奇异局势下先手必胜。
（a，b）表示两堆物品的数量，也称之为局势
奇异局势：就是当A面对这个局势时就已经输了。你也可以理解成必输局面。比如（0,0）或者（1,2）（3,5）等等
那怎么知道一个局势是否为奇异局势
a与b满足这个条件：
ak =[k（1+√5）/2]，bk= ak + k
（k=0，1，2，…,n 方括号表示取整函数）ak<bk

整合一下
ak = [ ( bk - ak ) （ 1 + √5 ） / 2 ]

证明：略（其实我也不是很明白）

代码：

        if(a>b)  swap(a,b);  
        ans=floor((b-a)*(1+sqrt(5.0))/2.0);  
        if(ans==a) cout<<"后手必胜"<<endl;  
        else cout<<"先手必胜"<<endl;

三.环形博弈

n个石子围成一圈，每次只能取相邻的k（1<=k<=n）个石子，取完者胜。
今天一个同学问我，我才想起来这个。。。

结论

如果n<=k,先手必赢（也就是如果先手能一次拿完就输）
当k等于1时，n为奇先手胜，n为偶后手胜。

证明

因为是环形，假如说A第一次没去完，那B只要取与A相对的石头，也就是A拿完后，还剩奇数个石头，B就拿与A对应位置的一个石头，如果剩偶数个，就拿对应位置的两个
这样就把一个环拆分成两个链，且每个链都是相等的
用sg定理，sg[x] ^ sg[x]= 0
这就是必败态，所以先手A输了
当k=1时，这就不用我讲了吧。。。

代码：

bool circle_game(int n,int k){
    if(k>=n||k==1&&(n&1)) return 1;
    return 0;
}

例题 HDU - 3951