参考资料：
- http://www.cnblogs.com/exponent/articles/2141477.html
- 朱全民《游戏策略》

nim游戏

nim游戏是ICG游戏

什么是ICG游戏？

• 两名选手交替进行操作，每次操作只能在一个固定的合法移动集合中操作
• 对于合法的移动集合，仅受到局面的影响，不收到当前轮到哪名选手操作影响，且操作无后效性
• 不能移动者判负

什么是nim游戏

有若干堆石子，通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

引入一些定义

• P-postion
  P is for ‘previous’
  指的是，先手必败，即后手必胜的局面
• N-position
  N is for ‘next'
  与前者相反
  

  更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position的局面是P-position。

瞎扯

WARNING：这个部分是pkl随便自言自语，没有任何依据，不保证正确性

I

对于一个nim游戏的局面$a_1, a_2, a_3, ..., a_n$, 后手必胜当且仅当$a_i$异或和为0
这个结论可以快速求出当前局面的状态是什么
是不是很niubi！！！
niubi！！！
niubiA！！！！
怎么就和异或扯上关系了！！！！！

• 若一个一个点的后继存在任意一个P，那么这个点是N，同样的，若一个点是N，那么它的后继一定存在一个P
• 若一个点的后继没有N，那么这个点是P，同样的，若一个点是P，那么它的后继一定没有N
  （这里窝说的后继是指可以转移到的局面QAQ

倘若结论对于状态的判定正确，那么结论的这个判定方法必须保证其判定的每一个状态节点：
1. 若一个点被判定为N，那么它的后继一定存在一个P
2. 若一个点被判定为P，那么它的后继一定没有N

满足了这两个条件，充分性似乎还稍少了点什么。。我们还需要一个类似递归出口一样的东西（不
3. 对于Terminal position判定为P-position

所以只需要证明这三个命题就可以证明结论的判定方法是否正确。

II

开始证明。
第三个命题很好证，因为我们的T-positon只有一个都是0的状态，异或起来还是0证（民）明（科）结束

剩下两个命题懒得码字了怎么办。可耻地粘一下下。

第一个命题:对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k

// 这里原来有一坨废话

第二个命题：对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。证毕。

至此，我们证明完了结（民）论（科）

http://blog.csdn.net/clover_hxy/article/details/53818624

一个更加具象的东西

下面是真`民科.jpg。。。。。。。
以下是pkl自己yy的，不保证正确性。

异或实际上是什么。
仔细想一想就是以一种十分巧妙的方法将两堆石子的情况扩展到n堆石子。
首先对于偶数堆有相同石子个数的局面一定是后手必胜（考虑两堆相同石子的情况然后扩展一下就可以的出来了。
现在考虑Pp异或等于0意味着什么。
对于第k个二进制位为1代表有一堆2^{k - 1}个石子的石子堆
异或和的第k个二进制位为0意味着什么,意味着有偶数堆2^{k - 1}的石子堆
这个时候在我们上面得出来的结论的基础上再yy一下，发现这个局面一定是后手必胜的，因为先手取什么后手都可以取一样的。

然后考虑它是怎么把每次的操作限制为合法的。
对于任意整数我们都可以用几个二的幂表示出来。
每一次异或出来的值k->0的这个k，我们每次可以取出来的这个k，用异或的方式巧妙地限制了一定存在一个堆有>=k个石子（不然的话最高位的那个1怎么来的）可以供我们取出来。这一条限制了数量。
限制在同一堆取是显然的。

所以异或就和nim有了一种巧妙的关系。。
虽然我并不知道他一开始是怎么想到这种联系的。。。
感觉真是有才啊。。。。
哎。。。
我好菜啊。。。。

Extend

对于每一堆限制至多取m个，我们只需考虑%m + 1后每堆的石子数。
因为你每一次先手拿k个后手就可以把剩下的补齐，局面就又回到了一开始的状态,所以只考虑它的余数.
这样的话就回到了最原始的nim游戏解法。

这种ICG游戏一般情况下每个局面我们之考虑它的状态,因为它不具后效性

网上都什么辣鸡资料，毁我青春.jpg。。。。。。。

正常的资料：
- （没有）
（不
算了。。。。。。

资料建议食用顺序：
1. http://www.cnblogs.com/exponent/articles/2141477.html
2. 朱全民《游戏策略》
3. 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》

= = 。。。。。。。。。。
那个论文。。。。。千万不要一上来就去刚= =。。。。。可能是我自己语文的问题我觉得它可能。。有点奇怪（不

我好菜啊QAQ= =