觉得博弈论这种东西，知道结论代码巨短无比，不知道结论当场去世……

Nim 博弈

问题表述

有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 个，两个玩家轮流操作，每个玩家每轮可以选择一堆石子，取走至少一个石子（也可以把一堆取光，但不能不取）。不能操作者判负。已知每方均采取最优策略，问先手还是后手必胜？

解法

定理：Nim 博弈先手必胜当且仅当 \(\bigoplus_{i = 1}^n a_i \neq 0\)。

证明：设 \(\bigoplus_{i = 1}^n a_i = x \neq 0\)，且 \(x\) 的最高位为 \(j\)，由异或的性质，显然存在一个 \(a_i\) 的第 \(j\) 位为 \(1\)，且 \(a_i \oplus x < a_i\)，我们选择第 \(i\) 堆，令 \(a_i = a_i \oplus x\)，由异或的相消性，此时 \(\bigoplus_{i = 1}^n a_i = 0\)，我们把这样一个局面留给了后手，而后手无论怎么操作异或和都会变成非零。而不能操作的局面，即全零的局面的异或和同样为 \(0\)，又因为我们每次都可以那样地把锅推给对方，因此先手必胜。

阶梯博弈

问题表述

有 \(n\) 阶阶梯从左到右从低到高排开，记地面为第 \(0\) 级，第 \(i\) 个阶梯上有 \(a_i\) 个石子，两个玩家轮流操作，每个玩家每轮可以选择一个阶梯，将其中的至少一个石子转移到左边的阶梯（或者地面）上。不能操作者判负。已知每方均采取最优策略，问先手还是后手必胜？

解法

定理：阶梯博弈等价于奇数阶的 Nim 博弈。

证明：如果上一步对方从一个偶数阶的阶梯移动若干个石子到奇数阶，那么我们就原封不动地在这一步把这些石子再移到左边的偶数阶上去，因此偶数阶的石子的移动不造成影响。而既然偶数阶不造成影响，那么从奇数阶转移到偶数阶的操作等价于从奇数阶取走了若干石子（如果我们不看偶数阶），这样最后偶数阶的石子会全部到地面上，而奇数阶无法操作者自然就输了，证毕。

例题：POJ 1704