Nim 游戏

基础模型

例题：CSES 1730

• 有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗，每个人一次可以从一堆里那任意个石子（至少拿一个），不能操作的人输掉。

• \(1 \le n \le 2 \times 10^5, 1 \le a_i \le 10^9\)。

• 暴力打表后发现没有什么规律，那就直接上结论吧。若 \(a_1 \oplus a_2 \oplus \dots a _n = 0\)，那么后手赢，否则先手赢。首先每堆石子都为 \(0\) 是众所周知一个必败态，如果一个状态的 \(a_1 \oplus a_2 \oplus \dots a _n = 0\)，那么一定可以通过一次操作使得 \(a_1 \oplus a_2 \oplus \dots a _n \ne 0\)；反之经过一次操作一定会使 \(a_1 \oplus a_2 \oplus \dots a _n = 0\)。