预备知识
基
基是线性代数中的一个概念，它是描述、刻画向量空间的基本工具。而在OI题目中，线性基描述的向量空间一般是异或空间。
向量空间
定义$(F,V,+,\cdot)$为向量空间，其中$F$为域，$V$为集合，$V$中的元素称为向量，$+$为向量加法，$\cdot$为标量乘法。
线性无关
对于向量空间中 $V$上 $n $个元素的向量组$ (\mathbf{v}1, \ldots, \mathbf{v}_n)$，若存在不全为 $0$ 的数 $a_i \in F$，满$a{1}\mathbf {v} {1}+a{2}\mathbf {v} {2}+\ldots +a{n}\mathbf {v} _{n} = 0$则称这 $n$个向量线性相关，否则称为线性无关。
线性组合
对于向量空间中 $V$ 上 $n$ 个元素的向量组 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$，其线性组合是如下形式的向量
$a{1}\mathbf{v}{1} + a{2}\mathbf {v} {2}+\ldots +a{n}\mathbf {v} {n}$其中 $a_1, \ldots, a_n \in F$a。一组向量线性无关$ \Leftrightarrow $没有向量可用有限个其他向量的线性组合所表示
张成
对于向量空间中 $V$ 上 $n$ 个元素的向量组$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$，其所有线性组合所构成的集合称为$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$的张成，记为$ \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$。
基
若向量空间 $V$ 中向量组 $\mathfrak {B}$ 既是线性无关的又可以张成 $V$，则称其为 $V $的基（basis）。
$\mathfrak {B}$ 中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。
性质
设 $\mathfrak {B}$ 是向量空间 $V $的基。则$ \mathfrak {B}$具有以下性质：
- $V$ 是$ \mathfrak {B}$ 的极小生成集，就是说只有 $\mathfrak {B}$ 能张成 $V，而它的任何真子集都不张成全部的向量空间。
- $\mathfrak {B}$ 是 $V$ 中线性无关向量的极大集合，就是说 $\mathfrak {B}$ 在 $V $中是线性无关集合，而且 $V$ 中没有其他线性无关集合包含它作为真子集。
- $V $中所有的向量都可以按唯一的方式表达为$ \mathfrak {B}$中向量的线性组合。
第三点尤其重要，感性的理解，基就是向量空间中的一个子集，它可以通过唯一的线性组合，来张成向量空间中所有的向量，这样就可以大大的缩小我们向量空间的大小。
线性相关性引理
如果$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$在 $V$ 中是线性相关的，并且 $\mathbf{v}_1 \neq 0$，则有至少一个 $j \in {2, \ldots, m}$使得下列成立：
- $\mathbf{v}j \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}{j - 1})$；
- 如果从 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 去掉第$j $项，则剩余向量组的张成仍然等于$ \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v_n})$。
线性基介绍(口胡)
线性基是维护了一个数集的某些信息的集合(?)。
它可以将原来大小为$\text{N}$的数集在只求$\text{Xor}$和时压缩为$64$。
换句话说，你原来的数集互相异或出来的数的集合等于线性基中的数互相异或出来的数。
( 还是很有用的东西。)
线性基求法
我在网上看线性基求法时，看到了如下两种线性基求法：
复杂度$O(64n)$
1
2
3
4
5
6
7for(int i=1;i<=n;i++)
for(int j=62;~j;j--)
if(a[i]>>j&1)
{
if(b[j]) a[i]^=b[j];
else {b[j]=a[i];break;}
}其中，$\text{a}$数组是原来的数集，$\text{b}$是线性基。
注意，这种求法求出的线性基是上三角矩阵。
复杂度$O(64^2n)$
1
2
3
4
5
6
7
8
9
10
11
12
13for(int i=1;i<=cnt;i++)
for(int j=62;~j;j--)
if(lop[i]>>j&1)
{
if(b[j]) lop[i]^=b[j];
else
{
b[j]=lop[i];
for(int k=j-1;k>=1;k--) if(b[k]&&b[j]>>k&1) b[j]^=b[k];
for(int k=j+1;k<=62;k++) if(b[k]>>j&1) b[k]^=b[j];
break;
}
}
可以发现，这种求法只比上面的求法多了两句话：
1
2for(int k=j-1;k>=1;k--) if(b[k]&&b[j]>>k&1) b[j]^=b[k];
for(int k=j+1;k<=62;k++) if(b[k]>>j&1) b[k]^=b[j];不难发现，这两句话是高斯消元的过程，这种线性基求法求出来的线性基是对角矩阵。