摘要：博弈论（Nim，）
公平组合游戏
定义
公平组合游戏（Impartial Game）：
游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。
下面开始玩游戏
巴什博弈
问题模型
两个人一堆石子轮流取，每次可以取 $[1,k]$ 个，先取完者胜。
手动模拟
假设每次只可以取 $1$ 或 $2$ 个
只有一个石子 先手胜
只有两个石子 先手胜
有三个石子 无论先手取一个还是取两个 都会败 此时后手必胜
有四个石子···
结论推导
将这一堆石子（假设有 $n$ 个）分成若干个 $3$ 个一堆的石子和一堆 $< 3$ 的石子；
如果 $n\bmod3=0$，那么假设先手从第 $x$ 堆中 取了 $y$ 个，那后手可以取 $3-y$ 个将这一堆取完，那么无论先手怎么取，后手都能将这一堆的石子取完，也就是取到最后一个石子的人一定是后手；
如果 $n\bmod3\not=0$，那先手就可以把那 $<3$ 的一堆取完，然后（让后手面对那必败的局面），必胜；
显然可以推广到取 $[1,m]$ 个石子。
威佐夫博弈
问题模型
两堆石子两个人，每次从任意一堆中拿任意多个，或者从两堆中拿相同多个，拿走最后一个的人获胜。
结论推导
威佐夫博弈不同于 Nim 游戏与巴什博奕，它的特殊之处在于不能将两堆石子分开分析。
从末状态开始分析：
首先 $(0,0)$ 是一个 N-pos，进而推得在二维坐标系上 $y=0$，$x=0$，$y=x$ 上的点为 P-pos（不考虑 $(0,0)$）。
再来考虑 $A1=(1,0)$，无论怎么转移都会移动到 P-pos，所以 $(1,0)$ 为 N-pos。
因为要准备数据结构，就先搁了QwQ
abs(a - b) * (sqrt(5) + 1.0) / 2.0 == min(a, b) ? puts("0") : puts("1");