zhongzihao/games
例题
来源：Part I, 1.5.3–Ferguson
题目大意：有一堆 \(31\) 颗的石子，每次可以取 \(1\sim6\) 颗，但是每种数量至多取 \(4\) 次。问胜负情况。
题解：不妨先不考虑 \(4\) 个的限制。这个比较简单，模 \(7\) 余 \(0\) 的状态是负态。然而如果先手按这种策略操作，只要后手一直取 \(4\)，先手最后一轮将无 \(3\) 可用。
事实上，先手先取 \(5\) 仍可保证取胜。如果后手一直也取 \(5\) ，先手取 \(2\) 来应对。取了 \(4\) 个 \(5\) 和 \(3\) 个 \(2\) 后，还剩 \(5\) 个，此时已经不能再取 \(5\) 了，因此后手不论怎么取都会输。如果后手某一回合不取 \(5\) 了，先手可以立即转移到模 \(7\) 余 \(0\) 的状态，可以验证这时不论如何先手不会没东西可用，因为开始的若干操作拖延了一回合。
例题
来源：Part I, 1.5.5–Ferguson
题目大意：有两堆石子，每次操作可以将某堆石子清空，然后把剩下的一堆石子分成两个非空的堆。问胜负情况。
题解：如果两堆石子都是奇数，那么先手负，否则先手胜。如果至少有一堆石子是偶数，那么我们可以把这堆石子拆成两个奇数堆，从而转移到负态。而如果两堆石子都是奇数个，显然拆出来至少有一个偶数。
例题
来源：Part I, 1.5.6–Ferguson
题目大意：给你一个矩形网格，每次选取一个格子，将该格子右上方的部分删除，删掉左下角格子的玩家输。证明除 \(1\times1\) 外，先手必胜。
题解：假如删掉右上角的格子后是负态，那么命题已经成立。否则后手一定可以进行某种操作转移到一个负态，而容易发现这个操作先手同样可以完成。
例题
来源：Part I, 1.5.7.a–Ferguson
题目大意：有一堆 \(n\) 颗的石子，先手可以任意取，但是不能取完，之后每个人至多只能取上一次取的数量。问胜负情况。
题解：我们首先归纳地证明，对于每个 \(k\ge0\)，如果当前石子数能被 \(2^{k+1}\) 整除，且至少能拿 \(2^{k}\) 个石子，那么当前这个人不会取 \(\le2^{k}\) 个石子。
\(k=0\) 时显然，如果先手只拿 \(1\) 个，那么之后所有人都只能拿 \(1\) 个石子，显然先手就输了。
假设 \(\le k\) 时成立。\(k+1\) 时，假如先手取了 \(x<2^{k+1}\) 颗石子，那么后手直接取 \(\text{lowbit}(x)\) 颗石子，我们已经证明了先手不能取 \(\le\text{lowbit}(x)\) 颗石子，而先手又没有其它选择，因此这样必败。假如先手取 \(2^{k+1}\) 颗石子，后手也同样取 \(2^{k+1}\) 颗石子，这样到最后先手还是会输。
这样一来结论就简单了。假如石子个数是 \(2\) 的幂，那么先手必败，因为后手可以取 \(\text{lowbit}\)。否则先手取 \(\text{lowbit}\) 即可。
例题
来源：Part I, 1.5.7.b–Ferguson
题目大意：和上一题大体相同，但是至多可以取上一次取的数量的两倍。
题解：首先介绍斐波那契进制，即将一个正整数表示为若干不相邻的斐波那契数之和，可以证明这样的表示是存在且唯一的。
设当前数的斐波那契进制表示为 \(a_{1}+\cdots+a_{n},a_{1}>\cdots>a_{n}\)。
假如 \(n\ge2\)，那么先手可以删掉 \(a_{n}\)，由于 \(a_{n-1}>2a_{n}\)，因此后手不能一次取完。我们来证明后手不论怎么取，仍然会回到刚刚的情况。假设后手取完后，\(a_{n-1}\) 变为了 \(b_{1}+\cdots+b_{m}=a_{n-1}-x\)，我们想要证明 \(2x\ge b_{m}\)。采用反证法，假设 \(2x<b_{m}\)，这样 \(x\) 的斐波那契进制表示必然和 \(b_{m-1}\) 不相邻，从而 \(a_{n-1}=b_{1}+\cdots+b_{m-1}+x\)，这样就与 \(a_{n-1}\) 的斐波那契进制表示唯一矛盾了。
假如 \(n=1\)，和刚刚相同可证得先手必败。
例题
来源：Part I, 1.5.8–Ferguson, 2017 ECL-Final L
题目大意：一个 \(1\times n\) 的格子，每次往一个空格子中填入 S 或 O，先填出 SOS 的胜。问胜负情况。
题解：我们称一个格子是好的，当且仅当其中填入 S 和 O 都将导致后手胜利。容易证明，这样的格子只会在 S**S 中出现。因此好格子是成对出现的，即最后只剩下好格子时，一定是偶数个。假如 \(n\) 是偶数，那么先手负，否则后手负。另外还需要证明对方一定能摆出好格子。
若 \(n\) 为偶数，且 \(n\ge16\)。假如先手摆 S，后手可直接摆出。否则先手摆 O，那么一定有一边有至少 \(8\) 个格子，后手在该侧离边界 \(3\) 个格子的地方摆 S，即 SXXX 或 XXXS（X 表示空格子）。如果先手在远离边界的一侧摆，那么后手也可以直接填出。如果先手在边界一侧摆，后手就可以在另一侧摆出 S**S，由于第一回合先手摆了 O，因此这样填不会陷入非法状态（注意如果先手先填 S 则不能保证）。
若 \(n\) 为奇数，且 \(n\ge7\)。先手在中间摆 S，不论后手什么操作，先手在另一侧填即可。
暴搜可以证明其它时候都是平局。\(n=14\) 的一个证明可以参见 Ferguson 的习题答案。
（ang 怎么出原题的啊
SG 定理
证明：假如当前异或和为 \(0\)，不论先手如何操作，都会恰改变一个 \(\text{sg}\)，因此异或和变为非 \(0\)。
假如当前异或和不为 \(0\)。考虑异或和的最高位，一定有某个 \(\text{sg}\) 该位为 \(1\)，该 \(\text{sg}\) 异或上异或和后一定变小，从而先手可以进行这样的操作，并转换成负态。
SJ 定理
定义使得所有 \(\text{sg}\) 变为 \(0\) 的人负（即使原游戏还可以进行操作）。证明胜态为：
- 若异或和为 \(0\)，所有 \(\text{sg}\le1\)
- 若异或和不为 \(0\)，至少有一个 \(\text{sg}>1\)
证明：
对于胜态：
若所有 \(\text{sg}\) 为 \(0\)，已经成立。
否则若异或和为 \(0\)，又至少有一个 \(1\)，把 \(1\) 变成 \(0\) 即可。
若异或和不为 \(0\)，若有至少两个 \(\text{sg}>1\)，那么按照 \(\text{SG}\) 定理行动即可。这样之后，至少还有一个 \(\text{sg}>1\)，因此是负态。若只有一个 \(\text{sg}>1\)，那么按照奇偶性决定将它变成 \(1\) 还是变成 \(0\)。
对于负态：
若异或和为 \(0\)，则至少有两个（不可能是一个）\(\text{sg}>1\)。不论怎么操作，异或和会变为非 \(0\)，而 \(\text{sg}>1\) 的至少还有一个，因此是胜态。
若异或和不为 \(0\)，则所有 \(\text{sg}\le1\)。把 \(0\) 变成 \(1\) 或 \(1\) 变成 \(0\) 均为胜态。而如果把某个 \(\text{sg}\) 变成 \(>1\)，由于只有一个 \(>1\)，异或和不为 \(0\)，因此还是胜态。
