[杭电多校4 | HDUOJ7184]Link is as bear（线性基模板）

题目传送门：Problem - 7184 (hdu.edu.cn)

题意 / Problem

给定一个数组，每次可以选择一段连续区间[l, r]并将区间内所有元素变为区间元素的异或和。问最终能够把整个数组变成的最大的数，要求所有数字都变成相同的。

思路 / Thought

线性基的板子，就是求一个数组的最大异或和。

线性基可以看这篇文章《[数学基础 & 模板]Xor Linear Basis异或线性基学习笔记》

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9, MAXL = 55;
int p[60], d[60], tot = 0, N, M;

void ins(int x)
{
	for(int i = MAXL;i >= 0; -- i)
	{
		if(!x)return;
		if(!(x >> i & 1))continue;
		
		if(p[i])x ^= p[i];
		else return p[i] = x, void();
	}
}

void rebuild()
{
	tot = 0;
	for(int i = 0;i <= MAXL; ++ i)
	{
		for(int j = 0;j < i; ++ j)if(p[i] >> j & 1)p[i] ^= p[j];
		if(p[i])d[tot ++] = p[i];
	}
}

int que_max()
{
	int res = 0;
	for(int i = 0;i < tot; ++ i)res ^= d[i];
	return res;
}

void solve()
{
	cin >> N;
	memset(p, 0, sizeof p);
	for(int i = 1;i <= N; ++ i)
	{
		int x;cin >> x;
		ins(x);
	}
	rebuild();
	cout << que_max() << '\n'; 
}

signed main()
{
	ios::sync_with_stdio(false);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}