题解：AT_arc219_d [ARC219D] Grid Game

Left_i_Forever · 2026-05-13 20:52:05 · 题解

神秘的博弈。

对于 i+j 为偶数的格子（下简称偶数格子，奇数格子同理），每次挪动到奇数格子后另一人都可以再将其挪动到另一个偶数格子上，所以偶数格子上的棋子实际是没有影响的。

那么对于奇数格子，我们只需要把上面的石子挪到偶数格子上，那么就可以把问题等价转换为 从若干堆石子中，每次选一堆取出 \left[1,k\right] 个石子，问谁最后把石子取完。这样的话可以先让每次先后手一回合拿走 k+1 个石子（类似巴什博弈），然后就是 Nim 游戏了。

所以所有奇数格子的石子数对 k+1 取模后异或起来，为 0 Bob 赢，否则 Alice 赢。

代码太短不给了。