定义
对于自然数集 $S$，$S$ 的线性基被定义为最小的集合 $R$，使得 $S$ 的任何一个子集的 $S’$，都能找到一个 $R$ 中的子集 $R’$，$S’$ 中所有元素的异或和等于 $R’$ 中元素的异或和，且对于 $R$ 的所有子集 $R’$，也能找到对应的 $S’$。
形象地说，$R$ 内元素随意异或得到的集合等于 $S$ 内元素随意异或得到的集合。
性质
- 线性基能相互异或得到原集合的所有相互异或得到的值。
- 线性基是满足性质 $1$ 的最小集合。
- 线性基内没有异或和为 $0$ 的子集（因为 $R$ 的空集的异或和为 $0$）。
线性组合
我们从另一个角度来考虑问题，即 $x$ 被表示为其他数的异或和代表什么。我们把 $x$ 拆成一个向量 $x=\{a_0,a_1,\dots,a_{k-1}\}$，$x=\sum{2^i\times a_i}$，其中 $k$ 是位数。
那么，$x$ 能被表示成 $S$ 的某个子集的异或和 转化为 $x$ 能被表示成 $S$ 中数所对应的向量在模 $2$ 意义下的线性组合。这样一来，$R$ 这个最的小能表示任何数的集合本质上就是 $S$ 的最大线性无关集合。
注意：这里的最小和最大并不矛盾，最小意味着线性无关，最大意味着能表示任何一个数。
现在，我们把数的异或，转换成了向量的线性组合。
求解
高斯消元时，如果某一行被前面的行消为 $0$，那么代表它可以被表示成前面向量的线性组合，这也就是为什么：
方程组有解、系数矩阵行列式不为 $0$、系数矩阵满秩、系数矩阵的线性无关集合大小为 $n$ ——这四个命题等价。
对于新加入的数 $x$，如果它能被表示成 $R$，就代表它能被 $R$ 消成 $0$。
我们把向量反过来写，把高位系数写在左边，低位系数写在右边，对所有数做高斯消元。最终矩阵会被消成一个上三角矩阵，剩下的不为 $0$ 的向量就是 $R$，而且每个向量（数）的最左边的非零数（最高位）都不相同。
因为矩阵行秩等于列秩，所以 $R$ 最多有 $k$（其中 $k$ 表示位数，一般为 $32$）个元素。
由于是在模 $2$ 的意义下，所以我们可以直接压位来做。记 $r_i$ 表示最高位为 $i$ 的线性基中的数。每次新加进来一个 $x$ 就从其最高位开始消去，如果某一位（假设为第 $i$ 位）无法消除了就把当前的 $x'$ 放进 $r_i$ 中，即 $x'$ 在线性基 $R$ 中。
时间复杂度：$\mathcal O(n \log w)$，其中 $w$ 为值域。
代码
#include <cstdio>
const int N = 1e6 + 5;
int n;
unsigned int a[N], r[32];
void Gauss(int n) {
for (int i = 1; i <= n; i++) {
unsigned int x = a[i];
for (int k = 31; ~k; k--) {
if (!(x >> k) & 1) continue;
if (r[k]) {
x ^= r[k];
} else {
r[k] = x;
break;
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%u", &a[i]);
}
Gauss(n);
for (int i = 0; i < 32; i++) {
if (r[i]) printf("%u\n", r[i]);
}
return 0;
}