【YBT2023寒假Day9 A】異或路徑（線性基）

異或路徑

題目連結：YBT2023寒假Day9 A

題目大意

有一個 n*m 的網格，然後你要從 (1,1) 走到 (n,m)，你的分數是你路徑上每個點的權值的異或和（出現多次就異或多次）。

每次可以選上下左右四個方向走，不能走出網格，問你分數最大值。

思路

首先如果隻能向右向下走你走的點的個數是确定是 n + m − 1 n+m-1 n+m−1。

考慮在這個基礎上加一些修改，會發現你如果要改一段路徑，你把那一段的路徑，和你要改成的路徑，它形成一個圈，那你直接異或上這個圈的值，就可以改路徑了。

那麼這樣的話，我們其實可以直接控制任意個數是否出現。

但是其實是錯的，你會注意到個數不是任意的。

考慮每個圈的長度都是偶數，而且有相同位置就消去每次也是消除 2 2 2 個（偶數個），是以你無論怎麼變換，個數的奇偶性都是 n + m − 1 n+m-1 n+m−1 的奇偶性。

于是考慮如何讓線性基選的數量的奇偶性固定。

于是考慮讓選奇數個更優或者偶數個更優。

那聯系上異或的性質，對于選奇數個我們可以給每個數賦一個很大的二次方值（比如 2 45 2^{45} 245），然後再丢進去跑線性基，出來的結果異或一下這個值即可。

那對于偶數，那你就在跑最大值的時候一開始是這個很大的數，就跟奇數一樣了。

代碼

#include<cstdio>
#define ll long long

using namespace std;

const int N = 5e5 + 100;
int n, m, tot;
ll a[N];

struct XXJ {
	ll f[64];
	
	void insert(ll x) {
		for (int i = 63; i >= 0; i--)
			if ((x >> i) & 1) {
				if (!f[i]) {
					f[i] = x; break;
				}
				x ^= f[i];
			}
	}
	
	ll get_max(ll fir) {
		for (int i = 63; i >= 0; i--) {
			if (!((fir >> i) & 1)) fir ^= f[i]; 
		}
		return fir;
	}
}p;

int main() {
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) scanf("%lld", &a[++tot]), a[tot] ^= (1ll << 45), p.insert(a[tot]);
	
	if (!((n + m - 1) & 1)) printf("%lld", p.get_max(1ll << 45) ^ (1ll << 45));
		else printf("%lld", p.get_max(0ll) ^ (1ll << 45));
	
	return 0;
}