一堆物品，一共有n个，每个人每次取1～m个，最后取光者获胜。
情况1: n = m+1，先手必败 情况2: n=(m+1)r + s，先手取s，后手取不超过m，所以先手可以继续取余数，使得总数满足(m+1)(r-1)，每次都把后手推到这个状态上，先手胜。
拍卖加价到目标值。原来是减，现在是加，但是原理是一样的。
n < m + 1 先手胜。 n = (m + 1)r + s，r>=1，s>0先手胜。 n=(m+1)r， r>=1,后手胜。
两个人轮流取[a, b]个
x< a必败 a<=x<b+a 必胜 (b+a)r + s 必胜
两堆物品，两人轮流取，要么从一堆里取，要么从两堆里取相同数目的物品，取的数目1～inf，最后取光着胜。
1、状态的表示 用(ak, bk)表示当前的局势，不失一般性ak<=bk 2、从简单状态开始研究 奇异局势（先手必败态） (0, 0), (1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20) 挑几个解释一下，就能发现规律 (0, 0) 显然没得取，所以输了 (1, 2) 如果之取一堆，那么对手把另一堆取完，输了。取两堆，只能剩一个，对手取，还是输了。 上面的状态可以拓展到(1, 3)、(1, 4)…(1, n)的情况，我只要从多的一堆取，然后留给对手(1, 2)我就赢了。这说明，每个局势中较小的数字不会重复，因为只要遇到了较小的数字，我就可以把较大的取走一部分，使之成为奇异局势留给对手。 (2, 3) 先手两堆各取一个，转化成(1,2)，从这个例子可以看到任何两个奇异局势小数和大数的差值不可能一样，否则只要两堆取一样的就能回到前一种。 因此奇异局势的规律是： 较小的数字是前面不会出现的最小数。bk = ak + k 3、三条性质 1、任何一个自然数都有一个必败态 2、任意操作都可以从必败态变成非必败态。 （只取一堆，改了一个数，任何数字只会出现在一个必败态，因为另一个数没变，所以不会出现在其他必败态，如果两堆都变了，差不变，必败态差都不一样，所以新局势一定不是必败态）。 3、适当的操作可以从非必败态变成必败态。 如果两个数字一样，直接取完，(0,0)是必败态 如果a=ak, b > ak + k，只要把多出来的b的部分取完就行(ak, bk)是必败态 其他情况不再赘述。 因为非必败态总是可以根据适当操作让对手下一轮面临必败态，所以非必败态就是必胜态。
ak = [ k ( 1 + 5 ) 2 ] [\frac{k(1+\sqrt5)}{2}] [2k(1+5 )]，bk = ak + k 这个推导很复杂，先把结论放这。
三堆物品，两个人轮流从一堆中取任意多的物品，最后取光着胜。
1、简单情况 (0, 0, 0)必败 (0, n, n)和对手拿一样多，先没得取的一定是对手，对称策略。 (1, 2, 3) case1 (1, 2, 3)->(0, 2, 3)->(0, 2, 2)后手胜 case2 (1, 2, 3)->(1, 2, 2)->(0, 2, 2)后手胜 case3 (1, 2, 3)->(1, 1, 3)->(1, 1, 0)后手胜 所以这是一个必败态 2、规律（其实不好推 直接放结论,会在下一节证明） 任何必败态，异或和为0。 3、获胜策略 如果是一个非必败态，那么只要让选择一个数是另外两个异或和，这样异或之后肯定是0，所以让对手陷入必败态。
上面问题的边式，堆数变成n，别的都一样
定义T态和S态。其中T态为异或和为0的状态。 1、任意S可以变成T 用A(i)表示第i堆的物品数 C=A(1)^A(2)…A(n) > 0 设C的最高有效位是第p位，存在t，A(t)[p] = 1(否则全是0，xor之后也是0，c[p]=0矛盾) x=A(t)^C, x < A(t) 因为第p位又两个1，异或之后是0，高于p位的部分没有变化，而如果把A(t)换成x，则有 A(1)XOR A(2)…XOR x XOR …A(n) = A(1) XOR A(2) XOR…XOR A(t) XOR C XOR A(t+1)…A(n) =0 所以只要从t堆取A(t)-x就可以实现。 2、任意T一定变成S 反证 假设T之后还是T 假设经过一番操作A(i)->A’(i) C = A(1)…A(i)…A(n) = 0 T态 C’ = A(1)…A’(i)…A(n) = 0 T态 C XOR C’ = A(i) XOR A’(i) = 0 A(i) = A’(i) 矛盾 综上，S可以变成T，T又总是变成S，所以T必败，S必胜。
异或和为0，必败，反之必胜
最后取完的人算他输。
1、两个定义 只有一个物品的堆，称为孤单堆，用SH（single heap）表示。 有超过一个物品的堆，称为充裕堆，用RH（rich heap）表示。 2、对S、T状态进行细分
对T状态 RH>=2,称为T2 RH = 0 称为T0 RH=1呢，称为T1？no不可能有T1，因为如果只有一个RH，其他堆都是孤单堆，异或和不等于0。因为孤单堆只能改变最低位，这样一个充裕堆对于其他位的改变异或之后都是1。 注意不管是T0 T2，SH一定是偶数，因为RH都不能影响最低位，所以最低位要想异或和为0SH就必须是偶数。
对S状态 RH=0，只奇数个SH，S0（有没有可能有偶数个SH？如果它有RH会被分到S1或者S2，否则，他没有RH，那异或和为0，不是S态。） RH=1，S1 RH=2，S2
3、研究细分的S和T态转化 首先，前面研究的没有细化过的S和T态的转化依然成立，搬运过来 assertion1 T之后一定变成S assertion2 S之后可以变成T 之后研究细分状态 assertion3 T0必胜 T0没有RH，又因为异或和为0，所以一定是偶数个SH，相当于每次一人取一根，先手必胜。注意现在变成最后取完的人输了。 assertion4 S0先手必败。 因为有奇数个SH，先手取完一堆后留给后手的状态是T0，所以必败。 assertion5 S1必胜 因为有一个RH，如果现在有奇数个SH，那么取完这个RH，留给对手S0，对手必败。如果有偶数个RH，取到只剩一个，留给对手S0，对手必败。 assertion6 S2不能一步变成T0 因为RH不能从2一下变成0. assertion7 S2可以一次变成T2 S可以变成T，S2有不能一步变成T0，所以S2只能一步变成T2 assertion8 T2只能变成S1或S2 T只能变成S，T2不能一步变成S0，所以T2只能一步变成S1或S2 assertion8 S2必胜 S2变成T2，T2变成S1，则必胜 T2变成S2，则可以再变到T2 4、上面很晕，可以自己画个图，接下来总结一下 必败态 S0 T2 必胜态 S1 S2 T0 N堆尼姆博弈 S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0) 反向N堆尼姆博弈 S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0) 最常见，或者说最复杂（物品最多的时候）就是S2状态，双方反复取，总会使先手获得S1状态，而S1只有一个RH，通过决定把它取光还是留一个，可以决定后面的走势，所以不论是取完获胜还是取完输，抢夺S1是制胜关键。
必败态 S0 T2 必胜态 S1 S2 T0
次数限制形同虚设，因为在每堆>m的时候会用Bash博弈，最后剩下的和Nim博弈一样
两个人轮流从N堆物品中取，一个人取了一堆中的物品（1～inf）后，如果还有剩余，可以把剩下的安排到其他任意的非空堆上。
必败态(1,1) 对于堆中物品的个数都是偶数，不论如何操作，对方只要和你操作相同就必胜。 这个挺麻烦。。。先放结论
堆数为偶数且堆中物品个数成对的，必败，否则先手必胜。
n个物品，第一次不能取完，至少取1个。 以后每个人至少一个，只多是上一次取的2倍。
这种博弈证明很麻烦，基本就是一个找规律题吧。
n为fibonacci数必败。
没有可以放的位置则输。 对称策略。有中心先手胜，反之后手胜。
[1] [2] [3]
