【模板】线性基

线性基

定义：给定数集\(S\)，以异或运算张成的数集与\(Span{S}\)相同的极大线性无关集，称为原数集的一个线性基。
线性基具有以下性质：

1. 显然，线性基是原数集的一个子集。
2. 线性基的张成集合中一般不包含有数字0。一般给定的数集中不会有0，否则在线性基中加入0即可。
3. 张成集合中的每个数都可以唯一表示成基的线性组合。这与第一点是统一的。
4. 将线性基中的一个元素通过“倍加变换”（在这里即异或上另一个元素），张成集合不变。
5. 线性基中每一个元素的最高位均不同。

由以上性质不难看出，线性基与线性方程组有一些相似之处。事实上，如果把原数集的每一个元素二进制拆分为多项式，把每一项的系数看作一个向量，将所有系数向量看作一个矩阵的行，那么这个构造出的矩阵就可以看作某个线性方程组的系数矩阵。也就是说，对这个矩阵施以异或意义下的初等行变换，即将某些行消成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