签到（线性基）

题目描述

有一个$n\times m$的网格，第$i$行第$j$列的格子我们记作$(i,j)$。每个格子上都有一个数字，$(i,j)$上的数字为ai,ja_{i,j}ai,j​。你现在在$(1,1)$，你想走到$(n,m)$处签到，每次你可以走到上下左右四个相邻的格子中的一个，当然，你不能走出网格。你现在的心情值为a1,1a_{1,1}a1,1​，你的心情飘忽不定，你每走一步，你的心情值就会异或上走到的格子上的数字。你希望你签到的时候心情最好，为此你可以任意绕远路，甚至可以走到签到处的时候暂时不签到。请你求出最大的心情值。

输入格式

第一行两个正整数$n,m$。

接下来$n$行，每行$m$个非负整数，其中第$i$行第$j$个整数表示ai,ja_{i,j}ai,j​。

输出格式

输出一个整数，表示答案。

输入样例

2 2
1 2
3 4

输出样例

7

数据范围

对于$30\%$的数据，$n,m\le 4$
对于另外$30\%$的数据，n,m≤100,ai,j≤1000n,m\\leq 100,a_{i,j}\\leq 1000n,m≤100,ai,j​≤1000
对于$100\%$的数据，n,m≤500,ai,j≤109n,m\\leq 500,a_{i,j}\\leq 10^9n,m≤500,ai,j​≤109

题解

前置知识：线性基

首先，因为可以到签到点而不签到，那么沿任意一条路到达签到点后，对于点$(i,j)$，我们可以沿任意一条路走到点$(i,j)$，然后原路返回。那么走一次之后，心情值就异或上了ai,j⊕an,ma_{i,j}\\oplus a_{n,m}ai,j​⊕an,m​。

如果我们不考虑an,ma_{n,m}an,m​，那么其他的$a$值其实是可以任意选来求异或和的。然后，我们发现选中的点的奇偶性是不变的，而从$(1,1)$走到$(n,m)$的路可以确定其奇偶性，那么

• 如果$n+m$是奇数，那么选中的点的个数为偶数
  • 若除了an,ma_{n,m}an,m​的被选中的点的个数为奇数，那么an,ma_{n,m}an,m​被选中
  • 若除了an,ma_{n,m}an,m​的被选中的点的个数为偶数，那么an,ma_{n,m}an,m​不被选中
• 如果$n+m$是偶数，那么选中的点的个数为奇数
  • 若除了an,ma_{n,m}an,m​的被选中的点的个数为奇数，那么an,ma_{n,m}an,m​不被选中
  • 若除了an,ma_{n,m}an,m​的被选中的点的个数为偶数，那么an,ma_{n,m}an,m​被选中

我们可以提前将所有不是an,ma_{n,m}an,m​的ai,ja_{i,j}ai,j​的值异或上an,ma_{n,m}an,m​，那么

• 如果选中的点的个数为偶数，那么答案就是异或和的最大值
• 如果选中的点的个数为偶数，那么答案就是异或和再异或an,ma_{n,m}an,m​后的最大值

那怎么求异或和的最大值呢？用线性基即可。

那么如何求异或和再异或an,ma_{n,m}an,m​后的最大值呢？在线性基中，将$ans$的初始值设为an,ma_{n,m}an,m​即可。

时间复杂度为$O(nm\log mx)$，其中$mx$为ai,ja_{i,j}ai,j​的最大值。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,ct,lst,ans,a[505][505],b[105],c[500005];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}lst=a[n][m];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]^=lst;c[++ct]=a[i][j];}}--ct;for(int i=1;i<=ct;i++){for(int j=30;j>=0;j--){if((c[i]>>j)&1){if(!b[j]){b[j]=c[i];break;}c[i]^=b[j];}}}if((n+m)%2==0) ans=lst;for(int i=30;i>=0;i--){if((ans^b[i])>ans) ans=ans^b[i];}printf("%d",ans);return 0;
}