题解：AT_arc219_d [ARC219D] Grid Game

· · 题解

考虑策略偷取。我们发现，如果一个格子 (i,j) 到 (1,1) 距离为偶数，那么先手随便走，后手只要跟着偷先手的走法，最后还是得让给先手操作，没有交换先后手，所以距离为偶数的格子对答案没有影响。

我们现在只考虑奇数的格子，这个就相当于每次取不超过 k 的 Nim 游戏（即为 Bachet 游戏）了。先手随便拿走，然后就到了偶数位置，移动到偶数位置就没影响了，所以可以看做删去若干石子。

而只能拿不超过 k 的 Nim 游戏，只要把每一堆石子数量 a_i 当做 a_i \bmod (k+1) 之后考虑原版 Nim 游戏即可。因为我先手拿 x 个丢掉，后手跟着拿走 k+1-x 个相当于局面不变轮到先手了。

而原版 Nim 游戏结论是判断石子的异或和是否为 0。故本题只要判断 i+j 为奇数的石子 a_{i,j} \bmod(k+1) 的异或和是否为 0。

https://atcoder.jp/contests/arc219/submissions/75703839