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;
}参考文献：
