在 N\times M 的方阵中每格恰有一枚棋子,给定的 K 枚为黑,其余为白。 Alice 先手,两人轮流操作:选择 1\le x_1<x_2\le N,\ 1\le y_1<y_2\le M ,翻转四个角 (x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2) 上的棋子,要求右下角 (x_2,y_2) 原本为白(其余三格颜色不限)。 轮到某人时若棋盘上没有白色棋子(无法操作),则该人输。双方均采取最优策略,请输出胜者。
第一行 T ;每组首行 N, M, K ,随后 K 行黑棋坐标。
每组一行 Alice 或 Bob。
Alice
Bob
4 2 2 0 2 2 1 2 2 3 3 3 1 1 2 2 3 3 4 5 1 2 3
Alice Bob Bob Alice
1\le T\le 10 , 1\le N,M\le 10^9 , 0\le K\le \min(NM,2\times 10^5) , \sum K\le 2\times 10^5 。
经典 Turning Corners:单枚白棋 SG 为 nim 积 (x{-}1)\otimes(y{-}1) ,整局 SG 为白棋贡献之异或。 利用 nim 积对 XOR 的双线性, N\times M 极大时仍可用 \mathrm{pre}(N)\otimes\mathrm{pre}(M)\oplus\bigoplus(x{-}1)\otimes(y{-}1) 在 O(K\log^2) 内求出。