Bash游戏
这很简单，手玩两组样例就找到规律了。
只有一堆石子，个数为 \(n\) 个，两名玩家轮流在石子堆中拿石子，每次至少取 \(1\) 个，至多取 \(m\) 个，最后一个取走石子的玩家为胜者。
实际上，\((m+1)\ |\ n\) 时必胜。
Nim游戏
\(n\) 堆物品，每堆 \(a_i\) 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜。
需要读者自行掌握 \(N/P-position\) 证明法。
请注意
结论：\(\bigoplus_{i=1}^n a_i = 0\) 后手必胜，反之先手必胜。
证明：
- \(P \to N\)：当 \(\bigoplus_{i=1}^n a_i = 0\)，如果取一个数变为 \(a_i^{\prime}\)，此时若有 \(\bigoplus_{i=1}^n a_i = 0\)，则 \(a_i = a_i^{\prime}\)，矛盾。
- \(N \to P\)：\(\bigoplus_{i=1}^n a_i = k\) 此时需要将 \(k\) 变为 \(0\)，只需找到一个 \(a_i > a_i \oplus k\) 即可，即 \((a_i >>\log_2 k)\&1==1\)。
证毕。
P1247 取火柴游戏 - 洛谷
该题考察设计 \(Nim\) 游戏的方案，属于是加强版模板。
NimK
\(NimK\) 实际上是 \(Nim\) 游戏的推广，一般情况。
\(n\) 堆物品，每堆 \(a_i\) 个，两个玩家轮流取走任意 \(k\) 堆的任意个物品，但不能不取，取走最后一个物品的人获胜。
记 \((x)_i\) 为二进制下第 \(i\) 位。
结论：\(\forall s,\Big(\sum_{i=1}^n (a_i)_s\Big) \pmod{k+1} = 0\) 先手必败。
证明：
-
\(P \to N\)：当 \(\forall s,\Big(\sum_{i=1}^n (a_i)_s\Big) \pmod{k+1} = 0\)，如果将一个二进制位变为 \(0\)，此时必须操作\(k+1\) 次，但因为只能操作 \(k\) 堆石子，矛盾。
-
\(N \to P\)：\(\forall s,\Big(\sum_{i=1}^n (a_i)_s\Big) \pmod{k+1} = b\) 此时需要将 \(k\) 变为 \(0\)，大多数人的证法是错误的，因为那样讨论可能超过 \(k\) 组这里补充正确证法。
假设我们枚举每一位，如果 \(\Big(\sum_{i=1}^n (a_i)_s\Big) \pmod{k+1} = b_s\)，需要改变。
我们设除去已经更改的 \(m\) 堆，剩下堆 \(i\) 位上 \(1\) 的总和为 \(sum\)。
若 \(sum\le k-m\)，此时我们可以将堆上的 \(1\) 全部拿掉，让后让拿 \(m\) 堆得 \(i\) 位全部为 \(0\)。
若 \(sum > k-m\)，此时我们可以在 \(m\) 堆中选 \(k+1-sum\) 堆，让后让 \(i\) 位全部为 \(1\)，此时一定有 \(k+1-sum<k+1-(k-m)<m+1\)，故可以选到。
证毕。