题意

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