定义:给定数集\(S\),以异或运算张成的数集与\(Span{S}\)相同的极大线性无关集,称为原数集的一个线性基。
线性基具有以下性质:
由以上性质不难看出,线性基与线性方程组有一些相似之处。事实上,如果把原数集的每一个元素二进制拆分为多项式,把每一项的系数看作一个向量,将所有系数向量看作一个矩阵的行,那么这个构造出的矩阵就可以看作某个线性方程组的系数矩阵。也就是说,对这个矩阵施以异或意义下的初等行变换,即将某些行消成0行,形成的新矩阵与原矩阵行等价。这给了性质5一个很好的阐释:每个元素的最高位对应的是该系数矩阵化为阶梯形后的主元位置,而主元可以将其他行的该项通过行变换消去,结合异或的性质就不难理解了。
以上基于线性代数的讨论表明,可以使用类似高斯消元的行化简算法求得原数集的一个线性基。把每个行向量压成一个数处理,时间复杂度\(O(n^2)\)。
代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
using namespace std;
long long p[70], x;
int n;
void insert(long long x) {
for (int i = 60; i >= 0; --i)
if ((x >> i) & 1) {
if (!p[i]) {
p[i] = x; break;
}
x ^= p[i];
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x, insert(x);
}
long long ans = 0;
for (int i = 60; i >= 0; --i)
if ((ans ^ p[i]) > ans) ans ^= p[i];
cout << ans;
return 0;
}
原文:https://www.cnblogs.com/TY02/p/12232383.html