博弈论初步
博弈论(入门，持续更新)
博弈论
(本来想发博客园的，但太晚了又没办法发首页（虽然发了也要被扯）) 顺便发到洛谷来得咕值
本篇只对尼姆博弈和巴什博弈进行介绍（其余博弈遇到了再加进去）
定义 ：博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分
支，也是运筹学的一个重要学科。博弈论 是二人在平等的对局中各自利用对方的策略变换自己的
对抗策略，达到取胜的目的。
1，巴什博弈
巴什博弈：只有一堆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）的倍数，就能最后获胜。这个游戏还可以有一种变相的 玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。对于巴什博弈， 那么我们规定，如果最后取光者输，那么又会如何呢？（n）%（m+1）==0则后手胜利
先手会重新决定策略，所以不是简单的相反行的 例如n=15，m=3 后手 先手 剩余 0 2 13 1 3 9 2 2 5 3 1 1 1 0 0 先手胜利 输的人最后必定只抓走一个，如果>1个，则必定会留一个给对手
上面是百度百科的解释，先手胜利的条件比较显然，后手胜利的本质便是先手取任意数把原本（n）%
（m+1）==0的形式转化为n=（m+1）r+s的形式，也就是把先手转化为后手；原本后手变为先手；
例题：洛谷好像没有巴什博弈的例题
从别的佬博客里搬运了几道
HDU1847
HDU2147
HDU2149
HDU2188
HDU2897
2，尼姆博奕
有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，
最后取光者得胜。
这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，
0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要
与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局
势，无论自己如何拿，接下来对手都可以将其变为（0，n，n）的情形。
计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号⊕表示这种运算，先看
（1，2，3）的按位模2加的结果：
1 =二进制01
2 =二进制10
3 =二进制11 ⊕
———————
0 =二进制00 （注意不进位）
对于奇异局势（0，n，n）也一样，结果也是0。
任何奇异局势（a，b，c）都有a⊕b⊕c =0。
注意到异或运算的交换律和结合律，及a⊕a=0，:
a⊕b⊕(a⊕b)=(a⊕a)⊕(b⊕b)=0⊕0=0。
所以从一个非奇异局势向一个奇异局势转换的方式可以是：
1）使 a = c⊕b
2）使 b = a⊕c
3）使 c = a⊕b 因此，我们得到结论 把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。 证明可以看一下下面这位佬的博客 链接
Anti-Nimm game (尼姆博弈的变形,反尼姆博弈)
以这道题为例洛谷 P4279 SHOI2008小约翰的游戏
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int t;
int a[1000];
int ans;
int n;
int sum;
int main(){
cin>>t;
while(t){
t--;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ans=0;
sum=0;
for(int i=1;i<=n;i++){
ans^=a[i];
sum+=a[i];
}
if(sum==n){
puts(sum&1?"Brother":"John");
// cout<<endl; 注意puts自带换行
}
else{
puts(ans?"John":"Brother");
// cout<<endl;
}
}
return 0;
}反nimm博弈和尼姆博弈又是不同的情况
我们对代码中运用方法进行证明和总结
分类讨论再将相同情况合并
1 当每一堆的石子数都为1时，当堆数为奇数时先手输，否则后手输
2 当有且有一堆石子的个数>=2其余均为单个石子时，我们可以通过调整使下一状态下的全为单个石
子且数量可为奇数可为偶数，故，无论是谁，遇到这个状态其必将胜利
3 当有至少2堆的石子数>=2
显然石子必然要在减少的过程中由3状态变为2状态，
因为2状态下存在大于等于2的那堆石子，所以可知2状态下异或和一定大于0（存在较高位）
假设我们3状态下异或和大于0，则我们可将下一状态的异或和变为0或者仍然大于0（证明过程和尼姆
博弈的过程相同）
假设我们3状态下异或和等于0，我们通过取石子，只能使下一状态的异或和大于0，
我们已知2状态下异或和大于0，所以当我们处于状态3且异或和大于0时，我们可以通过调整使
下一状态的异或和等于0，但下一状态只能让下下状态的异或和大于0，所以当处于第三种情况时，
若异或和大于0，那么先手一定胜利，等于0则先手失败。
我们进行一下总结，由于第一种情况与后两种情况无法进行合并，所以对第一种情况进行特判定
对2.3种情况进行合并，即大于0先手一定胜利。
证明完毕
完结撒花。
其实这只是博弈论很少一部分，本题好像由sj定理可以直接做？（但我不会）
sg函数也不会（sg函数的题很少），以后遇到再学吧.我还是太菜了（真）；