Bash Game

显然，对于问题有必败态 $n=m+1n\; =\; m\; +\; 1$。

设 $n=r\cdot (m+1)+sn\; =\; r\; \backslash cdot\; (m\; +\; 1)\; +\; s$，其中 $rr$ 为任意自然数，$s\le ms\; \backslash leq\; m$。

1. 考虑 $s\mathrm{\ne }0s\; \backslash neq\; 0$ 的情况：

• $r=0r\; =\; 0$，先手可以直接取完，先手必胜。
• $r\mathrm{\ne }0r\; \backslash neq\; 0$，对于先手总能构造局势 $n=r\cdot (m+1)n\; =\; r\; \backslash cdot\; (m\; +\; 1)$ 的局势给后手，直至 $r=0r\; =\; 0$，先手必胜。

2. 当 $s=0s\; =\; 0$，两者角色互换，后手总能构造必败局面给先手，先手必败。

结论：如果 $(m+1)\mathrm{\mid }n(m\; +\; 1)\; \backslash \; |\backslash \; n$，则先手必败，否则先手必胜。

Nim Game

小红与小明在玩游戏，一共有 $nn$ 堆物品，每堆中有 $a_{i}a\_i$ 数量的物品。

每次从某一堆中取物品，至多将这全部拿走，不能不拿，拿到最后一个物品的玩家获胜。

1. 定义一个 $nn$ 元组 ($a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash dots,\; a\_n$), 来描述游戏的一个局势。

• 任意改变 $nn$ 元组中元素的顺序，仍然代表同一个局势。
• 如果初始局面只有一堆，则先手必胜。
• 如果初始局势有两堆，且两堆数量相同，后手必胜。（对称性）

2. 定义局势加法：($a_1,a_2,\cdots ,a_{n}a\_1,\; a\_2,\; \backslash cdots,\; a\_n$) + ($b_1,b_2,\cdots ,b_{m}b\_1,\; b\_2,\; \backslash cdots,\; b\_m$) = ($a_1,\cdots ,a_n,b_1,\cdots ,b_{n}a\_1,\; \backslash cdots,\; a\_n,\; b\_1,\; \backslash cdots,\; b\_n$)。

​ eg. (3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)

3. 对于局势$A,B,SA,\; B,\; S$, 若 $S=A+BS\; =\; A\; +\; B$, 称 $SS$ 可以分解为“子局势” $AA$ 和 $BB$。（对称性）
4. 对于局势A，如果先手有必胜策略，称“S胜”；如果后手有必胜策略，称“S负”。

• 如果局面为 $SS$ 胜，那么存在一种策略 $S->TS\; ->\; T$，$TT$ 负。
• 如果局面为 $SS$ 负，那么对于任意一种策略 $S->TS\; ->\; T$，$TT$ 胜。

5. 给定一个局势 $SS$，可以分解成两个子局势 $AA$ 和 $BB$。

• 若 $AA$ 和 $BB$ 为一胜一负，则 $SS$ 胜。
• 若 $AA$ 负 $BB$ 负，则 $SS$ 负。
• 若 $AA$ 胜 $BB$ 胜，则有时 $SS$ 胜，有时 $SS$ 负。

6. 二进制不进位加法（异或$\oplus \backslash oplus$）与局势加法对比

​ 令 $A,BA,\; B$ 代表局势，小写字母 $a,ba,\; b$ 表示二进制数，那么：

• 若 $AA$ 和 $BB$ 相同，则 $A+BA\; +\; B$ 负；若 $a\mathrm{\ne }0a\; \backslash neq\; 0$ 且 $b=0b\; =\; 0$，则 $a\oplus b\mathrm{\ne }0a\; \backslash oplus\; b\; \backslash neq\; 0$。
• 若 $AA$ 胜 $BB$ 负，则 $A+BA\; +\; B$ 胜；若 $a\mathrm{\ne }0a\; \backslash neq\; 0$ 且 $b=0b\; =\; 0$，则 $a\oplus b\mathrm{\ne }0a\; \backslash oplus\; b\; \backslash neq\; 0$。
• 若 $BB$ 胜 $AA$ 负，则 $A+BA\; +\; B$ 胜；若 $a\mathrm{\ne }0a\; \backslash neq\; 0$ 且 $a=0a\; =\; 0$，则 $a\oplus b\mathrm{\ne }0a\; \backslash oplus\; b\; \backslash neq\; 0$。
• 若 $AA$ 负 $BB$ 负，则 $A+BA\; +\; B$ 负；若 $a=0a\; =\; 0$ 且 $b=0b\; =\; 0$，则 $a\oplus b=0a\; \backslash oplus\; b\; =\; 0$。

猜想：令 $f(S)f(S)$ 表示 $SS$ 局势的异或和，即 $a_1\oplus a_2\cdots \oplus a_n\mathrm{。}a\_1\; \backslash oplus\; a\_2\; \backslash cdots\; \backslash oplus\; a\_n。$

• 若 $f(S)\mathrm{\ne }0f(S)\; \backslash neq\; 0$，先手必胜。
• 若 $f(S)=0f(S)\; =\; 0$，后手必胜。

推导过程：

结论1. $a_1\oplus a_2\cdots \oplus a_n=p\mathrm{\ne }0a\_1\; \backslash oplus\; a\_2\; \backslash cdots\; \backslash oplus\; a\_n\; =\; p\; \backslash neq\; 0$，那么

证明：

• $\because p\mathrm{\ne }0\therefore p\backslash because\; p\; \backslash neq\; 0\; \backslash therefore\; p$ 二进制最高位为1；
• 设其最高位为第 $qq$ 位；
• 那么至少存在一个 $kk$，使得 $a_{k}a\_k$ 的第 $qq$ 位也是1；
• $a_k\oplus pa\_k\; \backslash oplus\; p$ 的第 $qq$ 位为0，所以 .

结论2. 若 $f(S)=0f(S)\; =\; 0$，无论先手如果操作，都有 $S\to TS\; \backslash to\; T$ 满足 $f(T)\mathrm{\ne }0\mathrm{。}f(T)\; \backslash neq\; 0。$

证明：

• 不妨设先手在第一堆取了 $xx$ 个，那么对于局势 $T=(a_1-x,a_2,\cdots ,a_n)T\; =\; (a\_1\; -\; x,\; a\_2,\; \backslash cdots,\; a\_n)$。
• 由于 $f(S)=a_1\oplus a_2\cdots \oplus a_n=0f(S)\; =\; a\_1\; \backslash oplus\; a\_2\; \backslash cdots\; \backslash oplus\; a\_n\; =\; 0$, 所以 $a_1=(a_2\oplus a_3\cdots \oplus a_n)\mathrm{。}a\_1\; =\; (a\_2\; \backslash oplus\; a\_3\; \backslash cdots\; \backslash oplus\; a\_n)\; 。$
• 故 $f(T)=(a_1-x)\oplus (a_1)f(T)\; =\; (a\_1\; -\; x)\; \backslash oplus\; (a\_1)$，而 $a_1-x\mathrm{\ne }{a}_{1}a\_1\; -\; x\; \backslash neq\; a\_1$，所以 $f(T)\mathrm{\ne }0f(T)\; \backslash neq\; 0$ 。

结论3. 若$f(S)\mathrm{\ne }0f(S)\; \backslash neq\; 0$，必然存在一种操作方式 $S\to TS\; \backslash to\; T$满足 $f(T)=0f(T)\; =\; 0$。

证明:

• 设 $p=f(S)=a_1\oplus a_2\cdots \oplus a_n\mathrm{\ne }0p\; =\; f(S)\; =\; a\_1\; \backslash oplus\; a\_2\; \backslash cdots\; \backslash oplus\; a\_n\; \backslash neq\; 0$。
• 由 $p\mathrm{\ne }0p\; \backslash neq\; 0$，那么存在 $kk$，使得 ，不放设 $k=1k\; =\; 1$，即
• 如果先行者将第一堆数量变为 $xx$，那么局势 $T=(x,a_2,\cdots a_n)T\; =\; (x,\; a\_2,\; \backslash cdots\; a\_n)$。
• 由于 $p=a_1\oplus (a_2\cdots a_n)p\; =\; a\_1\; \backslash oplus\; (a\_2\; \backslash cdots\; a\_n)$，所以 $a_2\oplus a_3\cdots \oplus a_n=p\oplus a_{1}a\_2\; \backslash oplus\; a\_3\; \backslash cdots\; \backslash oplus\; a\_n\; =\; p\; \backslash oplus\; a\_1$。
• 所以 $f(T)=x\oplus (p\oplus a_1)=0f(T)\; =\; x\; \backslash oplus\; (p\; \backslash oplus\; a\_1)\; =\; 0$。