CodeForces - 1451F Nullify The Matrix(尼姆博奕变形)

题目链接：点击查看

题目大意：给出一个 n * m 的矩阵 a，两个人在矩阵上玩游戏，每轮的操作规则如下：

1. 选择任意一个点 ( x1 , y1 ) 作为起点，需要满足 maze[ x1 ][ y1 ] != 0
2. 选择任意一个点 ( x2 , y2 ) 作为终点，需要满足 x1 <= x2 && y1 <= y2
3. 点 ( x1 , y1 ) 减少一个任意值 x ∈ [ 1 , maze[ x1 ][ x2 ] ]
4. 除起点外，起点到终点的任意一条路径上可以任意赋值

无法操作者记为失败，问先手必胜还是后手必胜

题目分析：条件非常多，不过其本质是操作 3 的减少任意值，这个可以理解为尼姆博弈中的取石子操作，所以考虑一种特殊情况，如果当且仅当任意一个副对角线上有数字时，其余位置全部为 0 时，此时就变成了一个尼姆博弈的情况了：

如上图所示，因为此时起点和终点只能选择同一个点，所以上述的四种操作简化成了只有操作 3，也就变成了一个中规中矩的尼姆博弈了

所以整张图可以斜着划分成 n + m 个尼姆游戏，只不这些尼姆游戏并不是相互独立的，而是互相影响的，接下来考虑两种局面：

1. 局面 S：所有的尼姆游戏的异或和都是 0
2. 局面 S'：存在着一个尼姆游戏的异或和不为 0

然后就是两个需要证明的结论：

1. 局面 S 在通过一次操作后只能变成局面 S'
2. 局面 S' 在通过一次操作后可以变成 S，也可以变成 S'

又因为 S' 是必败局面，所以如果只看初始局面的话，初始局面若是 S' ，那么先手可以控制局势，所以先手必胜，否则先手必败

简单证明一下上面的两个结论：

1. 因为此时的局面中，所有尼姆游戏的异或和均为 0，假设起点为 ( x , y )，因为操作 3 约束了点 ( x , y ) 一定需要被取走石子，所以显然 x + y 这个尼姆游戏的异或和一定不可能是 0 了
2. 因为此时的局面中，至少有一个尼姆游戏的异或和不为 0，所以我们选择 x + y 最小的，且异或和不为 0 的尼姆游戏中寻找起点，以点 ( n , m ) 这个点作为终点，利用操作 3 将 x + y 这个尼姆游戏的异或和控制为 0，然后利用操作 4 将其余异或和不为 0 的位置都控制为 0 即可，因为起点到终点的一条路径上一定覆盖了 x + y ~ n + m 的所有尼姆游戏

代码：
 

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110;int _xor[N<<1];int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);int w;cin>>w;while(w--){memset(_xor,0,sizeof(_xor));int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++){int num;scanf("%d",&num);_xor[i+j]^=num;}if(*max_element(_xor,_xor+n+m)==0)puts("Jeel");elseputs("Ashish");}return 0;
}