参考自《算法竞赛进阶指南》
(NIM)博弈：
(n)堆物品，第(i)堆物品有(A_i)个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品的人获胜。假设两人每一步都必然采取最优的策略。问先手是否必胜。
定理：
若先手必赢，那么当且仅当满足：(A_1 \,\, xor \,\, A_2 \,\, xor \,\, A_3 \,\, ... \,\, xor \,\, A_n != 0)
两个概念：
必败局面：若某一局面无论采取什么行动，都会输掉游戏，则称该局面必败。
必胜局面：若在某一局面下采取某种行动后可以使对手面对必败局面，那么优先采取此行动，那么这种局面叫必胜局面。
证明：
- 如果所有物品被取光，那么即(A_i = 0)，那么这是一个必败局面，则满足:(A_1 \,\, xor \,\, A_2 \,\, xor \,\, A_3 \,\, ... \,\, xor \,\, A_n == 0)
- 对于任意一个(A_1 \,\, xor \,\, A_2 \,\, xor \,\, A_3 \,\, ... \,\, xor \,\, A_n = x != 0)局面，那么我们应该证明它一定可以采取一定行动来出现(x = 0)的局面（即对手必败局面）。
- 设(x)的二进制表示下最高位的(1)在第(k)位，那么至少存在一堆石子(A_i)，它的第(k)位是(1)，显然(A_i \,\, xor \,\, x \,\, < \,\, A_i)，然后我们便可以从(A_i)中取走(A_i - A_i \,\, xor \,\, x)个石子，使这堆石子变为(A_i \,\, xor \,\, x)个石子，那么代入式子得：(x \,\, xor \,\, x = 0)
- 对于任意一个(A_1 \,\, xor \,\, A_2 \,\, xor \,\, A_3 \,\, ... \,\, xor \,\, A_n = x == 0)局面，那么我们应该证明无论采取什么行动都不可能出现出现(x = 0)的局面。
- 用反证法证明：假设(A_i)被取成了(A_i')，那么此时就应该满足(A_1 \,\, xor \,\, A_2 \,\, xor \,\, A_3 \,\, ... \,\, xor \,\, A_i', \,\, ... \,\, xor \,\, A_n != 0)，由于(A_1 \,\, xor \,\, A_2 \,\, xor \,\, A_3 \,\, ... \,\, xor \,\, A_n == A_i)， 那么则出现了(A_i \,\, xor \,\, A_i' == 0)得情况，说明(A_i == A_i')，那么这显然不对与题目要求“不能不取石子”矛盾。
Mex运算
设(S)表示一个非负整数集合。定义(mex(S))为求出不属于集合S得最小非负整数的运算，即：
SG函数
有向图中，对于每个节点(x)，设从(x)出发共有(k)条有向边，分别到达节点(y_1, y_2, ..., y_k)，定义(SG(x))为(x)的后继节点(y_1, y_2, ..., y_k)的(SG)函数值构成的集合，再执行(mex)运算，即：
整个有向图的(SG)函数就是图的起点的(SG),(SG(G) = SG(s))
那么多个有向图的游戏中，行动规则是任选一个有向图(G_i)，并在(G_i)中行动一步，那么类比于(NIM)游戏，如果满足：
那么此时是必胜局面，证明方法与(NIM)博弈类似
否则必败局面。
理解：
在一个没有出边的节点上，不能进行任何操作，那么它的(SG = 0)，此时就是必败局面。
对于一个节点的某一个后继节点(SG = 0)的情况，在(mex)运算后，该节点(SG > 0)，那么等价于当前局面是必胜局面，因为后继界面是必败界面。
对于一个节点的后继节点(SG)均不为(0)，在(mex)运算后，该节点(SG)值为(0)，那么当前就是一个必败界面。
理论部分结束！
后边新学知识我再补上。