公平组合游戏

正常规则的公平组合游戏中，

1. 没有后继状态的状态是必败状态 $\mathcal{P}$，
2. 一个状态是必胜状态 $\mathcal{N}$ 当且仅当存在至少一个它的后继状态为必败状态 $\mathcal{P}$，
3. 一个状态是必败状态 $\mathcal{P}$ 当且仅当它的所有后继状态均为必胜状态 $\mathcal{N}$。

对于第一条，如果玩家当前已经没有可选的行动，那么玩家已经输掉了游戏。

对于第二条，如果该状态至少有一个后继状态为必败状态，那么玩家可以操作到该必败状态；此时，对手面临了先手必败状态，玩家自己就获得了胜利。

对于第三条，如果不存在一个后继状态为必败状态，那么无论如何，玩家只能操作到必胜状态；此时，对手面临了先手必胜状态，玩家自己就输掉了游戏。

Nim 游戏中，状态 $(a_1,a_2,\cdots ,a_n)$ 是必败状态 $\mathcal{P}$，当且仅当 Nim 和

$$a_1\oplus a_2\oplus \cdots \oplus a_n=0.$$

对所有可能的状态应用归纳法：

1. 如果 $a_i=0$ 对所有 $i=1,\cdots ,n$ 都成立，该状态没有后继状态，且 Nim 和等于 $0$，命题成立。

2. 如果 $k=a_1\oplus a_2\oplus \cdots \oplus a_n\ne 0$，那么，需要证明该状态是必胜状态。也就是说，需要构造一个合法移动，使得后继状态为必败状态；由归纳假设，只需要证明后继状态满足 $a_1^{\prime }\oplus a_2^{\prime }\oplus \cdots \oplus a_n^{\prime }=0$。利用 Nim 和（即异或）的性质，这等价于说，存在一堆石子，将 $a_i$ 拿走若干颗石子，可以得到 $a_i\oplus k$，亦即 $a_i>a_i\oplus k$。

   实际上，设 $k$ 的二进制表示中，最高位的 $1$ 是第 $d$ 位。那么，一定存在某个 $a_i$，使得它的二进制第 $d$ 位是 $1$。对于相应的石子堆，就一定有 $a_i>a_i\oplus k$，因为 $a_i\oplus k$ 中第 $d$ 位为 $0$，更高位和 $a_i$ 一样。

3. 如果 $a_1\oplus a_2\oplus \cdots \oplus a_n=0$，那么，需要证明该状态是必败状态。由归纳假设可知，只要证明它的所有后继状态的 Nim 和都不是 $0$。这是必然的，任何合法移动将 $a_i$ 变为 $a_i^{\prime }\ne a_i$，就必然会使得 Nim 和变为 $a_i^{\prime }\oplus a_i\ne 0$。

游戏 $G$ 和 $H$ 的 和（sum），或称 游戏组合（combined game），记作 $G+H$，是指游戏

$$G+H=\{g+H:g\in G\}\cup \{G+h:h\in H\}.$$

对于游戏 $G$ 和任何必败游戏 $A\in \mathcal{P}$，都有 $G\approx G+A$。

按照定义，只需要证明对于任何游戏 $H$ 都有 $G+H\approx G+A+H$ 成立。

如果游戏 $G+H$ 有必胜策略，那么，游戏 $G+A+H$ 也有必胜策略。如果对手在子游戏 $A$ 中进行了移动，就进行移动，将它恢复至必败状态；否则，按照游戏 $G+H$ 中的必胜策略移动。这样一定能保证最终的胜利。

如果游戏 $G+H$ 是必败游戏，那么，游戏 $G+A+H$ 也同样是必败游戏。因为无论这一回合进行的是子游戏 $G+H$ 和子游戏 $A$ 中的移动，对手都可以在下一回合将相应子游戏恢复至必败状态。最终，先手玩家一定无法获胜。

游戏 $G$ 和 $G^{\prime }$ 等价，当且仅当 $G+G^{\prime }\in \mathcal{P}$ 是必败游戏。

如果游戏 $G$ 和 $G^{\prime }$ 等价，那么，$G+G^{\prime }\approx G+G$，而游戏 $G+G$ 是必败游戏。这是因为，对于先手玩家的任何操作，后手玩家都可以在另一个子游戏中采取相同的行动，最后一定是先手玩家无法移动。

反过来，如果 $G+G^{\prime }$ 是必败游戏，那么，由引理 1 可知，$G\approx G+(G+G^{\prime })=(G+G)+G^{\prime }\approx G^{\prime }$。

对于任何一个（有限）公平游戏 $G$，都存在 $n\in \mathbf{N}$，使得 $G\approx \ast n$ 成立。

要证明定理的结论，可以应用数学归纳法。设游戏 $G=\{G_1,G_2,\cdots ,G_k\}$。根据归纳假设可知，存在 $n_1,n_2,\cdots ,n_k$ 使得 $G_i\approx \ast n_i$，那么，可以考察游戏

$$G^{\prime }=\{\ast n_1,\ast n_2,\cdots ,\ast n_k\}.$$

将要证明的是，$G^{\prime }\approx \ast m$，其中，$m=\mathrm{mex}\{n_1,n_2,\cdots ,n_k\}$ 是没有出现在集合中的最小自然数。

第一步，需要说明 $G\approx G^{\prime }$。根据 引理 2，只需要证明游戏 $G+G^{\prime }$ 是必败游戏。不妨假设 $G\ne \ast 0$。如果先手玩家选择 $G_i$，那么后手玩家就可以选择 $\ast n_i$；反过来，如果先手玩家选择了 $\ast n_i$，后手玩家就可以选择 $G_i$。总之，在这两步操作后，游戏变为 $G_i+\ast n_i$，根据引理 2 和 $G_i\approx \ast n_i$，这是必败游戏。这就证明了 $G\approx G^{\prime }$。

第二步，需要说明 $G^{\prime }\approx \ast m$。根据 引理 2，只需要证明 $G^{\prime }+\ast m$ 是必败游戏。不妨假设 $G^{\prime }\ne \ast 0$。如果先手玩家选择了 $\ast n_i\in \ast m$，那么根据 $m$ 的定义，后手玩家就可以选择 $\ast n_i\in G^{\prime }$，将游戏局面变为 $\ast n_i+\ast n_i\in \mathcal{P}$，先手必败。如果先手玩家选择了 $\ast n_i\in G$ 且 $n_i<m$，那么，后手玩家可以选择 $\ast n_i\in \ast m$，游戏局面同样变为 $\ast n_i+\ast n_i\in \mathcal{P}$，先手必败。最后，如果先手玩家选择了 $\ast n_i\in G$ 且 $n_i>m$，那么，后手玩家可以选择 $\ast m\in \ast n_i$，游戏局面变为 $\ast m+\ast m\in \mathcal{P}$，先手必败。这就证明了 $G^{\prime }\approx \ast m$。

由等价关系的传递性可知，$G\approx \ast m$。这就完成了归纳，证明所有游戏 $G$ 都等价于一个单堆 Nim 游戏。

公平游戏 $G$ 中的一个状态 $x$ 对应的 Sprague–Grundy 函数值 $\mathrm{SG}(x)$ 满足

$$\mathrm{SG}(x)=\mathrm{mex}\{\mathrm{SG}(x^{\prime }):x^{\prime }\in x\}.$$

其中，$\mathrm{mex}(A):=min\{n\in \mathbf{N}:n\notin A\}$ 是没有出现在集合 $A$ 中的最小自然数。

公平游戏 $G$ 中的一个状态 $x$ 是先手必胜状态，当且仅当 $\mathrm{SG}(x)\ne 0$。

对于公平游戏 $G_1,G_2,\cdots ,G_n$，有

$$\mathrm{SG}(G_1+G_2+\cdots +G_n)=\mathrm{SG}(G_1)\oplus \mathrm{SG}(G_2)\oplus \cdots \oplus \mathrm{SG}(G_n).$$

因为 $\ast a_1+\ast a_2+\cdots +\ast a_n$ 就是石子数量为 $(a_1,a_2,\cdots ,a_n)$ 的 Nim 游戏，所以，根据 Nim 游戏的结论可知，游戏

$$\ast a_1+\ast a_2+\cdots +\ast a_n+\ast (a_1\oplus a_2\oplus \cdots \oplus a_n)$$

是先手必败的。根据 引理 2，有

$$\ast a_1+\ast a_2+\cdots +\ast a_n\approx \ast (a_1\oplus a_2\oplus \cdots \oplus a_n).$$

所以，有

$$\mathrm{SG}(\ast a_1+\ast a_2+\cdots +\ast a_n)=a_1\oplus a_2\oplus \cdots \oplus a_n.$$

设 $a_i=\mathrm{SG}(G_i)$，就有 $G_i\approx \ast a_i$，那么，利用 $\approx$ 的代数性质，有

$$(G_1+G_2+\cdots +G_n)+(\ast a_1+\ast a_2+\cdots +\ast a_n)=\sum _{i=1}^n(G_i+\ast a_i)\in \mathcal{P}.$$

所以，就有

$$\begin{array}{rl}\mathrm{SG}(G_1+G_2+\cdots +G_n)& =\mathrm{SG}(\ast a_1+\ast a_2+\cdots +\ast a_n)\\ & =a_1\oplus a_2\oplus \cdots \oplus a_n\\ & =\mathrm{SG}(G_1)\oplus \mathrm{SG}(G_2)\oplus \cdots \oplus \mathrm{SG}(G_n).\end{array}$$

游戏先手必败，当且仅当 $n\equiv 0(\mathrm{mod}k+1)$。

当 $n\not\equiv 0(\mathrm{mod}k+1)$ 时，只要取走 $nmod(k+1)\in [1,k]$ 枚石子，就能保证对手处于必败状态。因此，此时是先手必胜状态。

反过来，当 $n\equiv 0(\mathrm{mod}k+1)$ 时，那么，要么已经没有选择，要么自己取走 $k^{\prime }$ 枚石子后，对手紧接着可以取走 $k+1-k^{\prime }$ 枚石子，让自己回到必败状态。

作为 Sprague–Grundy 定理的应用，可以计算 $f(n)$ 为只剩下 $n$ 枚石子时，对应局面的 SG 函数值。

对于 $n\le k$，可以归纳地证明 $f(n)=n$。这与单堆 Nim 游戏相同，因为取走石子数目的限制没有发挥作用。对于 $n>k$ 时，可以证明 $f(n)=nmod(k+1)$，所以，有

$$f(n)=\mathrm{mex}\{f(n-k),f(n-k+1),\cdots ,f(n-1)\}.$$

这遍历了模 $k+1$ 的全体余数，除了 $nmod(k+1)$。因此，就有 $f(n)=nmod(k+1)$。

将每一堆石子的数目都表示为二进制数，并对每个数位 $d$，都统计有多少堆石子数目的第 $d$ 位是 $1$，并计算这个数目对于 $(k+1)$ 的余数。如果对于每个数位，这个余数都等于 $0$，那么先手必败；否则，先手必胜。

仿照 Nim 游戏的结论的证明，很容易证明本结论。设 $d$ 为余数不为 $0$ 的最高二进制位，且对应的余数为 $k^{\prime }\le k$。那么，必胜策略为，在石子数目二进制第 $d$ 位为 $1$ 的石子堆中，选择 $k$ 堆，并选择移走的石子数目恰好使得对手局面中，每个数位的余数都是 $0$。唯一需要说明的是，最后取走石子数量的选择总是可行的。

实际上，只要选定 $k^{\prime }$ 堆石子，每堆都取走 $2^d$ 枚石子，就能使得结果中，第 $d$ 位余数变为 $0$。对于更低的数位的余数，将这些余数随意摊派给某一个堆即可。

游戏先手必败，当且仅当奇数堆石子数量的 Nim 和 $a_1\oplus a_3\oplus \cdots \oplus a_{n-1+(nmod2)}=0$。

任何玩家将偶数堆的石子移动到奇数堆时，对手都可以将这些石子继续移动到下一个偶数堆（或移走），因此，这样的移动不会影响奇数堆的局面。此时，每一个奇数堆向下移动到相邻的偶数堆（或移走）都可以看作独立的单堆 Nim 游戏。根据 Sprague–Grundy 定理关于游戏的和的结论，阶梯 Nim 游戏的 SG 函数值，是这些子游戏的 SG 函数值的 Nim 和。这就得到上述结论。

游戏开始时，先手必败，当且仅当石子数目 $n$ 是 Fibonacci 数。

设 $q$ 为当前局面可移走石子数量的限额（quota）。那么，第一回合中，$q=n-1$；而之后的回合中，$q$ 是上次（对手）移走的石子数目的二倍。考察剩余石子数目 $n$ 的 Fibonacci 编码，也就是将 $n$ 唯一地分解为一系列不相邻的、正的 Fibonacci 数的和。需要证明的是，当前状态是必胜状态，当且仅当 $q$ 大于等于 $n$ 的分解中的最小 Fibonacci 数。

必胜策略是：如果可以，移走所有剩余石子；否则，移走分解中最小的 Fibonacci 数。由于分解中，次小的 Fibonacci 数一定严格大于最小的 Fibonacci 数的两倍，所以，只要处于必胜状态的当前回合取不走所有石子，对手在下一回合也取不走次小的 Fibonacci 数（也就是下一回合最小的 Fibonacci 数），对手一定处于必败状态。

反过来，如果当前处于必败状态，那么，设当前取走的数目为 $k$，它一定严格小于当前分解中的最小 Fibonacci 数 $F$。假设下一回合最小的 Fibonacci 数是 $F^{\prime }$，它一定也是 $F-k$ 对应的分解中最小的 Fibonacci 数。设 $F^{\prime }=F^{″}+F^{‴}$ 且 $F^{″}>F^{‴}$，也就是说，$F^{‴},F^{″},F^{\prime }$ 是 Fibonacci 数列中相邻三项。如果 $k<F^{″}$，那么，利用 Fibonacci 编码计算 $k+(F-k)$ 时，不需要进位，自然得不到 $F$。所以，一定有 $k\ge F^{″}$。这就说明，下一回合的限额 $2k>F^{″}+F^{‴}=F^{\prime }$，是必胜状态。

不妨设 $a_1\le a_2$，那么，先手必败，当且仅当 $a_1=\lfloor (a_2-a_1)\varphi \rfloor$，其中，$\varphi =(\sqrt{5}+1)/2$ 是黄金分割比。

设 $r,s>1$ 是两个无理数，且 ${\displaystyle \frac{1}{r}}+{\displaystyle \frac{1}{s}}=1$。那么，序列 ${\mathcal{B}}_r$ 和 ${\mathcal{B}}_s$ 构成正整数集 ${\mathbf{N}}_{+}$ 的一个分划。此时，它们也称为互补的 Beatty 序列。

设 ${\mathcal{A}}_r=\{kr:k\in {\mathbf{N}}_{+}\}$。考虑将集合 $\mathcal{A}={\mathcal{A}}_r\cup {\mathcal{A}}_{\ell }$ 里的元素排序得到序列 $\{a_i{\}}_{i\in {\mathbf{N}}_{+}}$。需要证明的是，$i=\lfloor a_i\rfloor$ 对所有 $i\in {\mathbf{N}}_{+}$ 都成立，就能得到 ${\mathcal{B}}_r\cup {\mathcal{B}}_s$ 是正整数集 ${\mathbf{N}}_{+}$ 的一个分划。

首先，证明序列里没有重复的元素。假设不然，存在 $k,\ell \in {\mathbf{N}}_{+}$ 使得 $kr=\ell s$ 成立。那么，有

$${\displaystyle \frac{\ell }{k}}={\displaystyle \frac{r}{s}}=r-1.$$

但是，等式左侧是有理数，等式右侧是无理数，矛盾。因此，序列的数字各不相同。

然后，证明集合 $\mathcal{A}$ 中小于等于 $a_i$ 的数恰有 $\lfloor a_i\rfloor$ 个。不妨设 $a_i\in {\mathcal{A}}_r$，即 $a_i=kr$，那么，对集合 ${\mathcal{A}}_r$ 和 ${\mathcal{A}}_{\ell }$ 中的元素分别计数，就得到小于等于 $a_i$ 的正整数恰有

$$k+\lfloor {\displaystyle \frac{kr}{s}}\rfloor =k+\lfloor k(r-1)\rfloor =\lfloor kr\rfloor =\lfloor a_i\rfloor$$

个。进而，由于序列 $\{a_i\}$ 是严格递增的，小于等于 $a_i$ 的数恰有 $i$ 个。这就得到 $i=\lfloor a_i\rfloor$。

对于所有 $a_1<a_2$ 且先手必败的状态 $(a_1,a_2)$，令 $k=a_2-a_1\in {\mathbf{N}}_{+}$，都有 $a_1=\lfloor k\varphi \rfloor$ 且 $a_2=\lfloor k(\varphi +1)\rfloor$。由于 $\varphi$ 是黄金分割比，所以 ${\displaystyle \frac{1}{\varphi }}+{\displaystyle \frac{1}{\varphi +1}}=1$。由 Rayleigh 定理可知，序列 $\{\lfloor k\varphi \rfloor \}$ 和 $\lfloor k(\varphi +1)\rfloor$ 构成正整数集 ${\mathbf{N}}_{+}$ 的一个分划。这其实说明，所有 $a_1<a_2$ 且先手必败的状态 $(a_1,a_2)$ 中，分量 $a_1$ 和 $a_2$ 恰取遍全体正整数一次，且它们的差 $a_2-a_1$ 也恰取遍全体正整数一次。

由于 Wythoff 游戏中，一次合法的操作要么保持分量之一不变，要么保持分量之差不变，所以，从一个先手必败状态开始，确实无法由一次合法的操作中得到另一个先手必败状态。反过来，对于任何先手必胜状态 $(a_1,a_2)$，不妨设 $a_1\le a_2$，并令 $k=a_2-a_1$。如果 $a_1>\lfloor k\varphi \rfloor$，那么，先手玩家可以从两堆石子各取 $(a_1-\lfloor k\varphi \rfloor )$ 枚，将局面变为必败状态。反过来，由前一段的结论，对于这个 $a_1$ 必然存在唯一一个必败状态 $(a_1,a_2^{\prime })$。进而，如果 $a_1>a_2^{\prime }$，显然有 $a_2^{\prime }<a_2$；否则，如果 $a_1<a_2^{\prime }$，那么，可以取 $k^{\prime }=a_2^{\prime }-a_1$ 使得 $a_1=\lfloor k^{\prime }\varphi \rfloor$，又有 $a_1<\lfloor k\varphi \rfloor$，故而 $k^{\prime }<k$，因此 $a_2^{\prime }=a_1+k^{\prime }<a_1+k=a_2$。所以，只要 $a_1<\lfloor k\varphi \rfloor$，就一定有 $a_2^{\prime }<a_2$，先手玩家只需要从第二堆石子中取走 $(a_2-a_2^{\prime })$ 枚石子就可以使得局面变为必败状态。

对于翻硬币游戏 $(S,f)$ 和局面 $G$，设其中正面朝上的硬币所处位置的集合为 $H(G)\subseteq S$。那么，局面 $G$ 的 SG 函数值就是

$$\mathrm{SG}(G)=\underset{s\in H(G)}{⨁}\mathrm{SG}(G_s).$$

考虑一个相关的游戏：一个局面 $G^{\prime }$ 中，集合 $S$ 的每个元素处都放置有若干枚石子；玩家每次行动时，都可以取走 $s$ 处的一枚石子，并选取集合 $T\in f(s)$，再在集合 $T\setminus \{s\}$ 中的各个元素处均放置一枚石子。对于这类游戏，仍然可以定义基础局面 $G_s^{\prime }$，即仅在位置 $s$ 处放置有一枚石子的局面。这类游戏中，每个局面均为其所有石子对应基础局面的和。这是因为只要放置新石子时将它对应到取走的石子上，就可以将游戏过程中出现的每枚石子都对应到初始局面中的各个石子上，进而对应初始局面不同石子的子游戏进程互不干扰，整个游戏就可以看作是这些子游戏的和。由于相同位置石子对应基础局面的 SG 值是一样的，所以利用异或值的特性可知，局面 $G^{\prime }$ 的 SG 值仅由各堆石子数量的奇偶性决定，而与具体数量无关。因此，对于游戏局面 $G^{\prime }$，如果记其石子数量为奇数的位置集合为 $H(G^{\prime })$，那么，本段的分析可以总结为公式：

$$\mathrm{SG}(G^{\prime })=\underset{s\in H(G^{\prime })}{⨁}\mathrm{SG}(G_s^{\prime }).$$

由此，下文只需要建立游戏 $G^{\prime }$ 与游戏 $G$ 的等价性就可以证明定理中的公式。

需要说明的是，对于新游戏的局面 $G^{\prime }$ 与翻硬币游戏的局面 $G$，只要 $G^{\prime }$ 中石子数量为奇数的位置与 $G$ 中硬币正面朝上的位置处相同，就有 $G^{\prime }$ 与 $G$ 等价。根据 Sprague–Grundy 定理的引理 2，这等价于证明局面 $G+G^{\prime }$ 是必败状态。后手玩家的胜利策略很简单：如果先手玩家选择取走 $s$ 处的石子且该处不止一枚石子，那么后手玩家直接模仿先手玩家的行为；否则，后手玩家选择和先手玩家同样的 $s$ 和 $T\in f(s)$，但是选择和先手玩家不同的子游戏，即先手取石子后手就取硬币，先手取硬币后手就翻石子。由于先手玩家无论任何操作，后手玩家就可以继续操作，并保证残余局面中石子数量为奇数的位置与硬币正面朝上的位置相同。这样，游戏必然结束在先手玩家没有合法操作时，因此，先手必败。定理由此得证。

游戏先手必胜，当且仅当顶点 $v$ 是图 $G$ 的最大匹配关键点，也就是说，在图 $G$ 的所有最大匹配中，顶点 $v$ 都是匹配点。

首先，顶点 $v$ 是图 $G$ 的最大匹配关键点。设 $G$ 的一个最大匹配为 $M$。此时，先手可以将局面移动到在 $M$ 中与顶点 $v$ 匹配的顶点 $u$。由于顶点 $v$ 出现在所有图 $G$ 的最大匹配中，所以，残余图 $G^{\prime }$ 的最大匹配的大小至多是 $|M|-1$；而且将 $M$ 去掉边 $(v,v)$ 就能得到图 $G^{\prime }$ 的一个大小为 $|M|-1$ 的匹配 $M^{\prime }$：结合这两点就知道，$M^{\prime }$ 是图 $G^{\prime }$ 的一个最大匹配。但是，后手玩家所处的局面中，顶点 $u$ 并不是匹配 $M^{\prime }$ 的一个匹配点。因此，后手玩家必然处于一个必败状态。

反过来，假设存在最大匹配 $M$ 使得 $v$ 是未匹配点。由于 $M$ 是最大匹配，与顶点 $v$ 相邻的顶点一定是匹配点；否则，就可以将它们之间的连边添加到 $M$ 中，得到一个更大的匹配。因此，无论先手怎么选择，后手都处于一个必胜状态。

反常 Nim 游戏中，状态 $(a_1,a_2,\cdots ,a_n)$ 是必败状态 $\mathcal{P}$，当且仅当

1. 存在 $i$ 使得 $a_i>1$，且 Nim 和 $a_1\oplus a_2\oplus \cdots \oplus a_n=0$，或者
2. 对于所有 $i$ 都有 $a_i\le 1$，且剩余的非空石子堆数是奇数。

由于无法操作是先手必胜态 $\mathcal{N}$，所以，可以归纳地证明，如果每堆石子都只有一枚，那么石子堆数是奇数就对应着先手必败态 $\mathcal{N}$，石子堆数是偶数就对应着先手必胜态 $\mathcal{N}$。

接下来，考察有些堆石子的数量严格大于 $1$ 的情况。

情形 A：如果只有一堆石子的数量严格大于 $1$，那么，此时 Nim 和一定不为 $0$。而且，由于先手玩家可以选择转移到全部堆的石子数量均不超过 $1$ 的局面，而且可以控制剩余的非空石子堆的奇偶性。因此，此时为先手必胜态 $\mathcal{N}$。

情形 B：现在，有不止一堆石子的数量严格大于 $1$，那么，无论怎么操作，下一个局面中，都至少有一堆石子的数量严格大于 $1$。根据归纳假设，下一局面中，先手必败对应着 Nim 和为零，先手必胜对应着 Nim 和不为零。这与正常 Nim 游戏的归纳假设完全相同。因此，重复 Nim 游戏的论证，就能知道，当前局面同样符合 Nim 和为零对应先手必败状态的结论。

显然，不同组石子堆的游戏相互独立，所以，只要计算每组游戏的 SG 函数值，就能计算出整个游戏的 SG 值，进而判断是否为必胜状态。关键在于如何计算每组石子堆的 SG 函数值。这并不容易。解决这类博弈论问题的常见思路是打表。设一组石子堆中石子数量分别为 $(i,j)$ 时，SG 值为 $f(i,j)$。那么，写一个暴力打表的程序，就得到如下结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 
1 1 2 2 1 1 3 3 1 1 2 2 1 1 4 4
0 2 0 2 0 3 0 3 0 2 0 2 0 4 0 4
2 2 2 2 3 3 3 3 2 2 2 2 4 4 4 4
0 1 0 3 0 1 0 3 0 1 0 4 0 1 0 4
1 1 3 3 1 1 3 3 1 1 4 4 1 1 4 4
0 3 0 3 0 3 0 3 0 4 0 4 0 4 0 4
3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 4
1 1 2 2 1 1 4 4 1 1 2 2 1 1 4 4
0 2 0 2 0 4 0 4 0 2 0 2 0 4 0 4
2 2 2 2 4 4 4 4 2 2 2 2 4 4 4 4
0 1 0 4 0 1 0 4 0 1 0 4 0 1 0 4
1 1 4 4 1 1 4 4 1 1 4 4 1 1 4 4
0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

这个表很具有规律性。有一个简单的观察：表格分成若干个 $2\times 2$ 的矩阵，且左上角处总是 $0$，而其余三个值总是一样的。于是，不妨将这个表格压缩，将每个 $2\times 2$ 的矩阵都压缩为除了左上角之外那个共同的数值：

1
2
3
4
5
6
7
8

1 2 1 3 1 2 1 4 
2 2 3 3 2 2 4 4 
1 3 1 3 1 4 1 4 
3 3 3 3 4 4 4 4 
1 2 1 4 1 2 1 4 
2 2 4 4 2 2 4 4 
1 4 1 4 1 4 1 4 
4 4 4 4 4 4 4 4 

可以发现，这个压缩的表格是前面完整表格相同位置的值加一。其实问题已经解决了。设下标从 $0$ 开始，那么表格中 $(i,j)$ 处的值 $g(i,j)$ 可以由如下递推公式给出：

$$g(i,j)=\{\begin{array}{ll}0,& \text{if }2\mid i\text{ and }2\mid j,\\ g(\lfloor i/2\rfloor ,\lfloor j/2\rfloor )+1,& \text{otherwise}.\end{array}$$

要求的 SG 函数 $f(i,j)=g(i-1,j-1)$。利用这一递推公式，算法可以在 $O(\log min\{i,j\})$ 时间内求出 $f(i,j)$ 的取值。

当然，可以通过简单的归纳法得到 $g(i,j)$ 其实就是将 $i$ 和 $j$ 反复同时除以 $2$ 得到两个偶数的最少次数。换句话说，它就是 $i$ 与 $j$ 的按位或中末尾 $1$ 的个数。由此，也可以直接利用 __builtin_ctz(~(i | j)) 算出该值。

这类题目中，只要通过打表观察的方法得到 SG 函数表达式，它都很容易通过归纳法证明，因而解题的关键在于以某种形式获得这些结论而非推导。例如，已知结论后，本题中的递推关系可以归纳证明如下。设 $S_k$ 为将 $k$ 枚石子分成非空的两堆能得到的局面的 SG 值集合，那么，$f(i,j)=\mathrm{mex}(S_i\cup S_j)$。故而，$S_k$ 有递推关系：

$$S_k=\{\mathrm{mex}(S_i\cup S_j):i+j=k,i,j\in {\mathbf{N}}_{+}\}.$$

需要证明的是，$d\in S_k$ 当且仅当 $(k-1)$ 的二进制表示中第 $d$ 位（最低位是第 $0$ 位）是 $1$。

利用数学归纳法。归纳起点 $S_1=\varnothing$ 显然成立。假设命题对小于 $k$ 的正整数都成立。那么，$d\in S_k$，当且仅当存在 $i,j\in {\mathbf{N}}_{+}$ 使得 $i+j=k$ 且 $(i-1)$ 和 $(j-1)$ 两个数的第 $d^{\prime }<d$ 位至少有一个为 $1$，且第 $d$ 位均为 $0$。显然，存在这样一种拆分，当且仅当只考虑第 $0\sim d$ 位的部分，即模 $2^{d+1}$ 时，$(k-1)=(i-1)+(j-1)+1$ 的取值范围为 $[2^d,2^{d+1}-1)$ 之间。这一条件就等价于 $(k-1)$ 的第 $d$ 位是 $1$。由此，归纳步骤成立。原命题得证。

对于这类问题，需要利用常见游戏的结论，并结合其他部分知识来进行解答。假设指定先手必须取走第 $i$ 堆石子，且指定的所有石子堆数量 Nim 和为 $v$，那么，先手无法获得胜利，当且仅当 $a_i\le a_i\oplus v$，也就是说，第 $i$ 堆石子数量 $a_i$ 不超过除第 $i$ 堆外剩余石子堆数量 Nim 和 $a_i\oplus v$。由于数据范围很小，直接枚举指定首轮取石子的堆；枚举到第 $i$ 堆时，剩余每个堆选或不选，可以得到不同 Nim 和的方案数可以通过 DP 计算出来，将最后得到的方案数中大于等于 $a_i$ 的部分加总起来即可。

由于本题中并不存在相互独立的子游戏，所有这道题目原则上只用到 判断必败和必胜状态的引理。从最简单的情形开始分析。当 $n\le 2$ 时，就是 Nim 游戏。当 $n\ge 3$ 时，问题变得复杂。但是，由于可操作的石子堆只能是两端的石子堆，不妨设它们中石子数量分别为 $x$ 和 $y$。进一步地，设 $f(x,y)$ 为先手必胜状态的指示函数，即先手必胜时 $f(x,y)=1$，否则 $f(x,y)=0$。容易发现，$f(x,y)$ 的取值满足递推关系：$f(x,y)=0$，当且仅当对于所有 $s<x$ 和 $t<y$ 都有 $f(x,t)=f(s,y)=1$。递推起点在 $x=0$ 或 $y=0$ 时，此时，游戏已经不足 $n$ 堆石子，需要进一步考虑中间石子堆的数量。因此，不妨暂时假设 $f(x,0)$ 和 $f(0,y)$ 是已知的，考虑如何从它们的取值推出所有 $f(x,y)$ 的取值。这并不困难。考虑下标集合为 $\mathbf{N}\times \mathbf{N}$ 的无穷大矩阵，求 $f(x,y)$ 相当于向里面填 $0$ 和 $1$，需要满足的条件是，每行和每列都至多一个 $0$，且如果同行或同列中之前的位置都没有出现过 $0$，该位置一定是 $0$。每行中 $0$ 的位置实际上定义了一个从行号 $x$ 到列号 $y$ 的函数。简单尝试几个例子（即打表）之后就可以发现，如果设使得 $f(x,0)=0$ 的唯一的 $x$ 是 $x_0$，使得 $f(0,y)=0$ 的唯一的 $y$ 是 $y_0$，那么，对于任何 $x$，使得 $f(x,y)=0$ 成立的

$$y=\{\begin{array}{ll}0,& x=x_0,\\ x-1,& x_0<x<y_0,\\ x+1,& y_0<x<x_0,\\ x,& \text{otherwise}.\end{array}$$

也就是说，只要知道 $x_0$ 和 $y_0$，就可以在 $O(1)$ 时间内计算出任意 $f(x,y)$ 的值，判断当前状态是否为先手必胜状态。而 $x_0$ 和 $y_0$ 可以递归计算。例如，$x_0$ 是使得 $f(x,0)=0$ 的唯一解，但同时，$f(x,0)$ 的取值可以通过移除最右侧石子堆后，只考虑剩下的 $n-1$ 堆石子来计算；也就是说，只考虑前 $n-1$ 堆石子，同样可以计算一个 $f_{1,n-1}(x,y)$，那么，显然有 $f(x,0)=f_{1,n-1}(x,a_{n-1})$；类似地，移除最左侧石子堆并计算得出 $f_{2,n}(x,y)$ 后，就得到 $f(0,y)=f_{2,n}(a_1,y)$。当然，内层的函数 $f_{1,n-1}(x,y)$ 和 $f_{2,n}(x,y)$ 的计算依赖于更内层的函数。这是典型的 区间 DP。每层只需要维护相应函数的 $x_0$ 和 $y_0$ 即可。