0. 前置芝士

定义状态

\(\text{P}\)：表示当前局面下先手必败。

\(\text{N}\)：表示当前局面下先手必胜。

\(\text{N,P}\) 状态的转移满足如下性质：

1. 合法操作集合为空的局面为 \(\text{P}\)。

2. 可以移动到 \(\text{P}\) 的局面为 \(\text{N}\)。

3. 所有移动只能到达 \(\text{N}\) 的局面为 \(\text{P}\)。

1. 问题

一共有 \(n\) 堆石子，第 \(i\) 堆中有 \(a_i\) 个石子。

每一次操作小 \(\mathtt{G}\) 和小 \(\mathtt{D}\) 可以从任意一堆石子中取出任意数量的石子，至少取一颗，至多取出这一堆剩下的所有石子。

两个人轮流行动，取走最后一个的人胜利。小 \(\mathtt{G}\) 为先手。

2. 结论

2.1. 内容

对于局面 \((a_1,a_2,...,a_n)\)，它是 \(\text{P}\) 局面当且仅当 \(a_1\ \text{xor}\ a_2\ \text{xor}...\text{xor}\ a_n=0\)。

2.2. 证明

容易发现只要满足以下三个条件即可：

1. 这个判断将最终态判为 \(\text{P}\) 局面。显然最终态全零。
2. 根据这个判断被判为 \(\text{N}\) 局面的局面一定可以移动到某个 \(\text{P}\) 局面。设异或和为 \(k\)，则一定存在 \(a_i\)，其二进制表示在 \(k\) 的最高位上是 \(1\)。由于二进制较高位上的 \(1\) 表示的十进制一定大于位数较低位上的 \(1\) 表示的十进制之和，则 \(a_i\ \text{xor}\ k< a_i\)（异或 \(k\) 也不会影响 \(a_i\) 的更高位）。那么我们将 \(a_i\) 改成 \(a_i\ \text{xor}\ k\)，异或和就变成 \(0\) 了。
3. 根据这个判断被判为 \(\text{P}\) 局面的局面无法移动到某个 \(\text{P}\) 局面。异或和为 \(0\) 只能异或 \(0\) 即取 \(0\) 个石子，故无法移动到某个 \(\text{P}\) 局面。

经典 Nim 游戏

原文：https://www.cnblogs.com/AWhiteWall/p/14403827.html