【写在前面】：
    趁着GDKOI还没考，先把这些奇怪的坑填上
    想写博弈论纯属意外，本来在做SDOI的题目，做了一道叫做黑白棋的题目
    然后发现不会，去搜了一发题解，发现是Nim游戏的变种
    然后把这种变种查了一下，有发现了一堆变种TAT，然后就入坑了QwQ
    不管了，既然选择就不能放弃嘛~
【参考】：

http://blog.csdn.net/acm_cxlove/article/details/7854530

    一些国家集训队的论文都已经包含在爱神的blog里面了，就不赘述了
【SG模型】：
    其实解决博弈问题有一类通用方法，就是利用SG函数
    什么是SG函数捏？百度百科的定义是这样滴：
    “对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。”
    也就是说我们把任何的博弈看成是一个图，每一个博弈的局面看成是一个点，然后如果局面A可以转化为局面B，那么就在图上连一条有向边，那么博弈游戏就转化为一张有向无环图，那么就有了上面的定义
    考虑SG函数有啥用捏？百科上的那些P-position和N-position太麻烦了，你可以直接记住结论：sg(x)=0说明局面x先手必败
    本着严谨的态度我还是来证明一发吧：（注意：mex(S)表示集合S中最小没有出现过的自然数）
    对于图中任意结点它的sg值不外乎两种情况：sg(x)=0和sg(x)!=0（额⊙▂⊙好像是废话TAT）
    我们考虑对于sg(x)不为0的点，也不外乎两种情况：后继集合为空或者后继集合中的点sg都不为0
    而对于sg(x)!=0的点，只有一种情况：后继集合中存在一个点sg=0
    以上性质十分显然，就不详细说了，现在我们来证明sg!=0的局面为先手必胜态，sg=0的局面为先手必败态
    1.我们考虑先手面对着一个sg不为0的局面，显然先手可以把这个局面移动一个sg=0的局面，然后后手捏？他只能把局面移动到一个sg!=0的局面，因为sg=0的局面的后继局面都是sg!=0，所以后手很无奈咯QwQ。因此无论怎么样，先手总有后继局面不为空（为空的话sg=0），而后手捏？如果不为空还好，但是毕竟是无环图啊，总有一天会变成空集滴。所以捏，先手必胜！
    2.如果先手面对着一个sg为0的局面，那么相当于先手后手换一下名字，然后就变成了上面的情况，先手必败！
    呼呼～终于证明完了。
    然后我们考虑一个问题，如果这个问题是由多个局面组合而成，那么整个问题的sg等于每个局面的sg的异或和
    为啥博弈游戏回合二进制异或扯上关系捏？其实我也不知道啊TAT，详细证明可以参考张一飞的《由感性认识到理性认识——透析一类搏弈游戏的解答过程》
    从以上我们看出：对于任意的博弈问题都可以用SG函数解决...个鬼啊！
    注意在OI考试中题目是有时间空间限制的，对于有些问题，我们很难在规定的时空限制内推出局面的SG值，因此对于一些特殊的题目，我们需要归纳出特殊的模型从而特殊的解决问题（一口气这么多“特殊”我也真是厉害啊TAT）
【Anti-SG模型】：
    定义：
    1.决策集合为空的决策者胜
    2.其它的规则和普通SG游戏相同
    现在有应该怎么解决呢？我直接给出答案好了
    前提：当某个子问题的sg=0时游戏结束
    1.存在某个子问题的sg>1，且整个问题的sg!=0
    2.所有子问题的sg=1，且整个问题sg=0
【Multi-SG模型】：
    定义：
    1.一个单一游戏的后继可以是多个子游戏
    2.其余的和普通SG游戏相同
    其实捏，我也不太明白这类游戏是什么鬼TAT
    我上网找了一道例题，也不知道是不是这种类型的：
    给出一行N个格子，先手后手轮流话'X'，首先连成3个的人赢
    我们考虑一下对于先手如果碰到X_X或者_XX或者XX_的状态就赢了
    所有我们在对方画了一个X后，这个X左右各两个格子的位置都不能话X，否则对手就赢了
    因此每画一个X，想到于把两边各两个格子去掉，然后转化为两边的子游戏，我们把两边的子游戏SG分别求一下异或起来就是后继局面的SG了。（难道这就是所谓的“一个单一游戏的后继可以是多个子游戏”？）
    SG函数记忆化搜索一下即可
【Every-SG模型】：
    定义：
    1.对于没有结束的单一子游戏，决策者必须分别都进行一次决策
    2.其余与普通SG游戏相同
    有这样一个策略：我们能赢的子游戏要尽量长时间的玩下去，我们必败的子游戏最好尽量早的结束
    因此我们定义step(x)为局面x的最优完成步数，然后我们分情况讨论：
    1.sg(x)=0，显然我们希望x尽早结束：step(x)=min(step(y)+1) y是x的后继局面且sg(y)!=0
    2.sg(x)!=0，显然我们希望x晚点结束：step(x)=max(step(y)+1) y是x的后继局面且sg(y)=0
    3.x为终止状态，step(x)=0
    因此我们得出结论：先手必胜当且仅当单一游戏中最大的step为奇数

Nin游戏是最基础的博弈论问题，下面有几种Nim游戏的变种，我将不再给出详细证明

如果有需要可以自行查找论文

【Nim游戏】：
    什么是Nim游戏呢？我给出一种通俗的定义：有N堆石子，先手后手轮流取，每次从一堆中取出若干个不能不取，取走最后一个的人获胜，问先手是否有必胜策略？
    我们考虑用SG函数解决，定义sg(a1,a2,...,an)表示一个局面，ai为第i堆石子的个数，然而我们发现对于N<=1000000的数据范围我们SG函数无能为力，难道SG函数不是万能的吗？
    显然不是，我们坚信SG函数是万能的，错就错在我们求SG函数的手段。
    其实对于这样一个问题，我们可以将他继续分解，把它变成有1堆石子，他有ai个，询问先手是否有必胜策略。
    对于这样一个游戏，它的sg值就是是石子数，即sg(ai)=ai。这很显然，sg(i)=mex(sg(0),sg(1),...,sg(i-1))=i
    然后我们利用上面的结论，整个游戏的sg值就是每个子问题的sg异或和，也就是说：
    sg(a1,a2,..,an)=sg(a1)^sg(a2)^...^sg(an)=a1^a2^...^an
    至此，这个问题解决了，求出一个局面的sg后，如果为0，那么先手必败，如果sg不为0，那么先手必胜
    我来简单的证明一下：假设sg!=0，那么我们一定可以找到一堆石子，我们拿去若干个，使得sg=0，那么后手面对着一个sg=0的局面，他只能到达一个sg!=0的局面。而终止态的sg=0，所以先手可以永远不可能面对sg!=0，并且使得后手永远是sg=0，因此后手总有一天会输的！
【K-Nim游戏】：
    定义：每次最多只能取K个，问先手是否有必胜策略
    在这种问题中，一堆石子的sg为ai%(k+1)，整个游戏的sg就是石子的sg函数异或和
【S-Nim游戏】：
    定义：每次取得个数只能是给定集合S中的数字，问先手是否有必胜策略
    在这个问题中，只能暴力sg，利用定义mex得到sg，然后异或起来就可以了
【Anti-Nim游戏】：
    定义：每次可以取任意个（不能不去），取最后一个的人输，问先手是否有必胜策略
    先手必胜有以下两种：
    1.所有堆的石子数都为1，且sg=0
    2.不是所有堆的石子数都为1，且sg!=0
【阶梯Nim游戏】：
    定义：一个n阶台阶，每个台阶上有若干石子。每次选择一个台阶上若干石子向下移动一个台阶，将最后一个石子移动到地上的人获胜
    结论：对奇数的台阶上的石子做Nim游戏即可
【NimK游戏】：
    定义：每次从不超过K堆的石子中取任意数量的石子，问先手是否必胜
    结论：将每一堆石子数变成二进制，统计每一位上1的个数即为cnt[i]，将cnt[i]对(K+1)取模，如果全都是0则必败，否则必胜

翻硬币问题也是一个很经典的问题

【翻硬币问题】：
    一般定义：
    1.每次按照一定约数条件翻：如连续的若干枚
    2.每次翻得的硬币最右边一定是从正面翻成反面
    3.无法操作者输
    结论：局面的SG值为各个正面朝上的硬币单一存在是局面的异或和
    我们用0表示反面，用1表示正面
    例如：sg(0011001)=sg(001)^sg(0001)^(0000001)
    以下给出几种不同约束条件下单一游戏sg值（sg(i)表示有i个硬币即左边i-1个反面最后一个正面的sg值）
    由于sg(0)=0，如无特殊情况，我们忽略0
    1.每次翻一个硬币：sg=1
    2.每次翻任意一个或两个硬币：sg值为编号
    3.每次连续K个：sg值从1开始为000…01 000…01，其中一小段0的个数为K-1
    4.每次翻了一个x后，必须在x-1 x-2 x-3任选一个翻动：sg从1开始为12301230...
    5.每次翻动两个，距离为1或2或3：sg从1开始12301230...
    6.每次翻动1或2或3个，当x的二进制有偶数个1时sg(x)=2*x+1，有奇数个1是sg(x)=2*x。注意这是特殊情况，sg(0)=1
    7.每次翻动连续任意个至少一个，sg(x)为x中2的最大次幂，如sg(16)=16 sg(12)=4
【二维翻硬币问题】：
    约定坐标范围[0..n-1,0..m-1]
    一般定义：
    1.每次翻一个连通快，且所有点都要在最右下方那个点的左上方
    2.每次翻得的硬币最右下那个一定是从正面翻成反面
    3.无法操作者输
    结论：局面的SG值为各个正面朝上的硬币单一存在是局面的异或和
    给出sg：
    sd(i,j)=lowbit(i+j+1) (i=0||j=0)
    sg(i,j)=2^(i+j) (i,j!=0)

还有一部分是删边问题，分为三种：

1.树删边

2.仙人掌删边

3.无向图删边

【树上删边游戏】：
    定义：
    1.每次删去一条边，将不与根节点连通的部分删去
    2.不能这么做的人输
    结论：
    1.叶子节点的sg为0
    2.非叶子结点的sg为子节点的sg+1后的异或和
    我们只要证明只有一个儿子结点成立，那么多个儿子结点变成了Nim游戏，全部加1后异或和就是答案
    我们利用书柜证明只有一个儿子结点成立：
    1.1个2显然成立
    2.假设K成立，那么证明K+1成立
      我们去掉一条边，一定是剩余的点<=K
      假设去掉根节点和唯一儿子的边，显然后继局面sg=0
      假设去掉唯一儿子子树中的边，那么在那个子树中sg=P，由于<=K是成立，那么sg就是P+1
      因此当前局面的后继局面sg值为0,1,2,..,sg+1
      得证！
【仙人掌删边游戏】：
    1.对于奇数的环，sg=1
    2.对于偶数的环，sg=0
    因此我们将偶数的环删去，将奇数环变成长度为1的短链
    然后变成一棵树辣！
【无向图删边】：
    有一个著名的结论：
    1.将原图的偶数环变成一个点
    2.将原图的奇数环变成一条边+一个点
    所有与原来环相连的边全部连到点上
    然后变成一棵树辣！并且树的sg与无相图的sg相同

呼呼～终于完结了

其实大部分都是摘抄爱神blog的内容TAT

不过自己也算是领略的不少新的姿势

希望对今后的解题有所帮助

完结撒花！