【CF1451F】Nullify The Matrix

题目

题目链接：https://codeforces.com/problemset/problem/1451/F
给出一个 (n imes m) 的网格，每个格子上有一个非负数。
两人轮流操作，每次操作选择一个数字大于 (0) 格子 ((x,y)) 开始，将 ((x,y)) 减去一个正整数，并且修改完后 ((x,y)) 依然非负。
然后选择一条从 ((x,y)) 开始只往右和往下的路径，到任意格子结束，并且将除 ((x,y)) 以外所有格子修改为一个非负数。
最先无法操作的人获胜。问先手是否必胜。
(Qleq 10,n,m,leq 100)。

思路

考虑横纵坐标之和相同的格子形成的一条条斜线，如果选择了格子 ((x,y))，那么它可以控制到所有 (x+y<k) 的斜线 (k) 的异或和。
找到第一个异或和不为 (0) 的斜线，根据 NIM 游戏的证明我们知道，只要选择异或和中最高位为 (1) 的那一个将它减小至异或和，这样就使得异或和变为 (0)。
除此之外，我们操作了这个格子之后还可以改变后面所有斜线的异或和，所以如果存在一条斜线的异或和不为 (0)，我们就可以通过一次操作把所有斜线的异或和变为 (0)。
接下来后手操作一定会变回存在一条斜线异或和不为 (0) 的情况，而目标状态异或和为 (0)，所以我们只需要判断初始状态是否存在一条斜线的异或和不为 (0) 即可。
时间复杂度 (O(Qnm))。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=110;
int Q,n,m,x,xors[N*2];

int main()
{
	scanf("%d",&Q);
	while (Q--)
	{
		memset(xors,0,sizeof(xors));
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				scanf("%d",&x);
				xors[i+j]^=x;
			}
		x=0;
		for (int i=1;i<=n+m;i++)
			x+=xors[i];
		if (x) printf("Ashish
");
			else printf("Jeel
");
	}
	return 0;
}