题意

Alice 和 Bob 在玩取石子游戏。

\(n\) 堆石子,\(a_1, a_2, \ldots, a_n\) 表示每堆石子的个数,\(b_1, b_2, \ldots, b_n\) 代表每堆石子的约束类型。

Bob 每次可以从其中一堆中取走任意数量的石子。

\(b_i = 0\),Alice 可以从该堆中取走任意数量的石子。

\(b_i = 1\),Alice 只能从该堆中取走奇数数量的石子。

\(b_i = 2\),Alice 只能从该堆中取走偶数数量的石子。

无法取石子的人输,Alice 先取石子,问谁必胜?

\(1 \leq n \leq 10^5\)\(1 \leq a_i \leq 10^9\)\(0 \leq b_i \leq 2\)

保证所有测试数据中 \(n\) 的和不超过 \(10^6\)

题解

定义 Alice 取石子不受限制的堆为普通堆,即 \(b_i = 0\) 的堆和 \(b_i = 1\)\(a_i = 1\) 的堆。

定义 Alice 取石子受限制的堆为特殊堆,即 \(b_i \neq 0\)\(a_i \geq 2\) 的堆。

引理:若只有一个特殊堆 \(i\),且 \(b_i = 1\)。设除堆 \(i\) 之外堆的石子个数异或和为 \(sg\),且 \(sg = a_i\),设所有堆的石子个数异或和为 \(all \_ sg\),即 \(all \_ sg = sg \wedge a_i = 0\)。Bob 先手,则 Bob 必胜。

证明:初始值 \(sg = a_i \geq 2\),Bob 先手维持 \(a_i = 2\)。根据 Nim 游戏可知,Alice 每取完一次石子,必须保证 \(all \_ sg = 0\),才有可能获得胜利。所以 Alice 第一次取完石子后,\(sg = a_i = 2\)。因为 Bob 维持 \(a_i = 2\),所以 Alice 无法从第 \(i\) 堆取 \(1\) 个石子,否则 \(a_i = 1\)\(all \_ sg \neq 0\),Bob 胜。所以 Alice 只能从其他堆中取走石子,但是此时 Bob 维持 \(a_i = 2\),从而使得自己最后将第 \(i\) 堆全部取完。

若不存在特殊堆,该游戏等价于 Alice 先手的 Nim 游戏。

若只有一个特殊堆

  1. \(b_i = 2\):如果 Alice 一次无法取完 \(a_i\),即无法使得所有堆成为普通堆,则 Bob 必胜,因为 Bob 可以将第 \(i\) 堆石子个数维持在 \(1\),最后自己取走。否则,等价于去掉第 \(i\) 堆石子后,Bob 先手的 Nim 游戏。
  2. \(b_i = 1\):如果 Alice 一次无法取完 \(a_i\) 且无法使得 \(a_i = 1\),即无法使得所有堆成为普通堆,由引理可知 Bob 必胜。否则,等价于去掉第 \(i\) 堆石子,或是第 \(i\) 堆石子个数为 \(1\),Bob 先手的 Nim 游戏。

若存在大于等于两个特殊堆,Bob 一定可以维持一个满足 \(b_i = 2\)\(a_i = 1\) 或者 \(b_i = 1\)\(a_i = 2\) 的堆,由只存在一个特殊堆的结论可知,Bob 必胜。

综上所述,如果 Alice 无法通过一次操作使得所有堆成为普通堆,则 Bob 必胜,否则转换成相应的 Nim 游戏求解。

comments powered by Disqus