博弈论基本知识
1、定义P-position和N-position：其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“先手必败”（奇异局势），现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”（非奇异局势）。
（1）无法进行任何移动的局面（也就是terminal position）是P-position；
（2）可以移动到P-position的局面是N-position；
（3）所有移动都导致N-position的局面是P-position。
2、P/N状态有如下性质：
（1）若面临末状态者为获胜则末状态为胜态否则末状态为必败态。
（2）一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。 （3）一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态
参考资料：
https://blog.csdn.net/xumingyang0/article/details/80274164
https://blog.csdn.net/acm_cxlove/article/details/7854526
https://blog.csdn.net/qq_40507857/article/details/81274426
https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html
一、巴什博奕（Bash Game）
问题
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
题解
若n=k*(m+1)，那么先手必败。
在n=k*(m+1)的情况下，先手无论拿多少，假设先手拿了x个吧，后手只要拿m+1-x个，让整体还是保持为(m+1)的倍数，最后一定会来到m+1的情况，而m+1是先手必败
例题
HDU4764 Stone
二、 威佐夫博弈（Wythoff Game）
问题
有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
题解
直接说结论了，若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5.0）+1）/2）*z ]；
若w=x，则先手必败，否则先手必胜。
例题
三、 尼姆博弈（Nim Game）
问题
尼姆博弈指的是这样一个博弈游戏：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
题解
把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。
例题
四、 斐波那契博弈
问题
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
题解
结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）
例题
HDU2516
巴什博奕 威佐夫博弈 斐波那契博弈 NIM 阶梯博弈， SG，找规律 树上博弈、