CF1451F Nullify The Matrix 题解
题目链接：Nullify The Matrix
题意：
Ashish 和 Jeel 在玩游戏，有一个 $n\times m$ 的棋盘，每个格子有一个非负整数的权值。
两个人轮流操作，每次操作先选择一个权值非 $0$ 的格子作为起点，然后选择起点右下角的一个格子作为终点，然后选择它们之间的一条最短路径，然后给起点的权值减一个正整数、路径上每个点的权值随意加减（也可以不改变），但是都不能改成负数。
不能操作（全变成 $0$）就输了，Ashish 先手，问谁必胜。
这道题的思路和 CF1149E 挺像的。
记 $f_i = \bigoplus_{x+y=p}a_{x,y}$ ，那么先手必败当且仅当 $\forall i$ 有 $f_i = 0$ ；否则先手必胜。
证明 记 $\rm N$ 为先手必胜态，$\rm P$ 为先手必败态。
考虑证明在此最优策略下原问题转化一个有向图游戏。
终止状态，显然为 $\rm P$ 。
对于 $\rm P$ 态，即 $\forall i, f_i = 0$ 时，任意修改都会导致某个 $f_i\ne 0$ 。那么 $\rm P$ 的后继均为 $\rm N$ 。
对于 $\rm N$ 态，即 $\exists i, f_i \ne 0$ 时，我们找到最小的 $i$ ，它对应第 $i$ 个斜线
取这个斜线二进制最高位所在的那个 $a_{x,y}$ 为起点，然后类似于那道题一路改过去就好了。$\square$
时间复杂度 $\mathcal{O}(n^2)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(233))
int a[N];
void solve()
{
memset(a, 0, sizeof(a)); int n, m; cin >> n >> m;
rep(i, 1, n) rep(j, 1, m) { int x; cin >> x; a[i + j] ^= x; }
rep(i, 2, n + m) if(a[i]) return cout << "Ashish\n", void(0);
cout << "Jeel" << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int qwq; cin >> qwq; while(qwq--) solve();
return 0;
}参考文献：
