也是头一次在打算法竞赛的时候想起久远的线代知识，线性基本身是构造了一个极大无关组，保证了在线性基的个数最少的情况下能得到对于一个数组里任意两个数的异或值，值一定都要是正数，如果原数组存在0 ，就额外标记一下，构造的方法就像依次去找线性基每一位是否存入，如果没有存入就该位为1的元素，如果已经存在数字，就把已经存在的数字异或的结果存进去，线性基可以通过普通消元得到，也可以通过高斯消元得到,线性基其实也是一种精简之后的异或高斯消元，它只考虑主元。线性基经常用来解决求自由选数的异或极大小值，甚至衍生到尼姆博弈的变形。
下面是一般线性基的代码：
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXBIT = 60;
int base[MAXBIT + 2];
//插入一个数x到线性基
void insert(int x)
{
for(int i = MAXBIT; i >= 0; i--)
{
if((x >> i) & 1)
{
if(!base[i])
{
base[i] = x;
break;
}
x ^= base[i];
}
}
//x最后变成0，代表该数可以被现有基异或表示
}
//求集合能得到的最大异或值
int get_max()
{
int res = 0;
for(int i = MAXBIT; i >= 0; i--)
{
if((res ^ base[i]) > res)
res ^= base[i];
}
return res;
}
//判断x是否可以由线性基中的数异或得到
bool exist(int x)
{
for(int i = MAXBIT; i >= 0; i--)
{
if((x >> i) & 1)
{
if(!base[i]) return false;
x ^= base[i];
}
}
return true;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; i++)
{
int x; cin >> x;
insert(x);
}
cout << get_max() << endl;
return 0;
}
一些杂谈：在处理或优化时候复杂度的时候，有几种大概的思路，数学结论推导，举个简单的例子，对于1累加到n,更优的O(1)算法是直接用公式而不是循环，在做题时可以考虑自己推导一下可能的公式；只存入有效元素处理，对于很多问题可能N的范围是1e5，o(n²)肯定会超时，但经常观察可能会发现不是每个元素都有存入的必要，这个元素如果不会影响最终的结果，可以只存入有效值；剪枝判断，在得到已经确定的结果之后直接退出循环；更换底层容器，例如map可以实现O(1)查询，优先队列可以维护数组的最大/小值，栈和队列可以保证数组的顺序。