acm-(Nim博弈)Codeforces Round #685 (Div. 2) F. Nullify The Matrix

传送门
本题题意就是两个人相互对一个矩阵进行操作：

1. 选定一个起点$(r_1,c_1)$,一个终点$(r_2,c_2)$，满足$r_2\ge r_1,c_2\ge c_1$。
2. 减少$a[r_1][c_1]$的值
3. 选择起点到终点的一条最短路径，路径上除了起点之外的点上的值随意分配(增加、减少或不变)

当某一方无法操作就输掉博弈。

我们对所有的点分个类，对于$r+c$相同的点分为一类，也就是矩阵上的一条斜线。那么我们更改最短路径上的点的值，实际上就是从$r_1+c_1$这条斜线到$r_2+c_2$这条斜线上某些点的值。不妨考虑令$sum[r+c]$为斜线上所有元素的异或和，当$\forall x\in [1,n+m],sum[x]=0$的时候就是必败局面，当$\exists x\in [1,n+m],sum[x]\ne 0$的时候是必胜局面，为什么这是正确的呢。

假设当前是必胜局面，我们必然能够将它转化为必败局面。首先找到最小的$x$使得$sum[x]\ne 0$，根据$Nim$博弈的原理，我们必定能够在$r+c=x$这条斜线上找到一个元素，减少这个元素的值使得$sum[x]=0$(不会$Nim$博弈看这里)，然后从这个元素的位置出发，我们随便走一条路径到终点，经过每条斜线的时候都看看当前的$sum$是否为0，如果为0就保持元素值不变，否则让该元素值改变(注意可以任意改变它的值)使得$sum$为0即可，这样最终我们可以让所有的$sum$值为0。

假设当前是必败局面，显然无论怎样操作，一定会起始点的斜线的$sum$变得不为0。

注意到当全局为0的时候符合必败局面的定义，故这个想法是正确的。

再看看博弈是否会结束，显然是会结束的，考虑每次选择的起点，都会将某个斜线上的值减少，并且，总有一次会选择最小的斜线进行操作，最终最小的斜线上的$sum$全会变成0，然后是第二小的斜线…最终所有的斜线的$sum$都会变成0

int sum[maxn];
int main(){int t=rd();while(t--){memset(sum,0,sizeof(sum));int n=rd(),m=rd();FOR(i,0,n)FOR(j,0,m){int u=rd();sum[i+j]^=u;}bool flag=1;FOR(i,0,n+m-1)if(sum[i]){wrsn("Ashish");flag=0;break;}if(flag)wrsn("Jeel");}
}