首先需要明确：

线性基处理的是向量，而我们在 OI 常用的“线性基”其实是其的一个变种——“异或线性基”。

线性基处理的是向量，具体的：

如果我们称 $n$ 个向量 $\vec{a}$ 是线性无关的，当且仅当 $\nexists c[1,n]$ 满足 $\exists p\mid c_p\ne 0$ 且 $\sum\limits_{i=1}^n c_i\times \vec a_i=\vec 0$，换而言之就是不存在这些向量之间可以相互表示。

那么对于一堆维度一样的向量，有他们构成的极大线性无关的向量构成的集合，我们称其为线性基。

需要注意，这里的极大指的是如可向内加入元素就一定要添加，并非所有的集合中最大的。

有方法可以证明，对于所有的线性基，其大小是一样的。

显然对于一个其中元素维度为 $n$ 的线性基，其元素的数量最大为 $n$，否则我们可以通过构造的方法得到满足条件的 $c$ 数组。

考虑一位一位考虑是否合法，然后将合法的加入，于是维护一个向量数组 $\vec a_i$ 表示目前的线性基，那么我们可以通过如下步骤进行判断。

假设现在需要加入的向量为 $\vec v$，那么：

• 如果 $v=0$，那么代表 $v$ 与前面的元素线性相关，结束操作。
• 如果 $a_i$ 不存在，则 $a_i\gets v$，结束操作。
• 否则，令 $\vec v\gets \vec v-\frac{\vec v_x}{\vec a_{i,x}}\times \vec a_i$。

容易理解通过这样的方法构造出的线性基是一个类似于上三角矩阵的东西，于是每一次进行操作 $3$ 都会至少消掉 $1$ 维，这也证明了为什么线性基大小最大只有 $n$。

但是这种处理向量的题目在 OI 中非常少见，我们常用的都是异或线性基，其将一个 $n$ 维的向量中具体值都限制在 $\{0,1\}$ 中，且所有的操作都是在模 $2$ 的意义下进行的。

那么我们就可以将其理解为不进位的加法，或者说是异或。

于是就有异或线性基中的元素满足：

$\nexists c_i\mid \exists p,c_p=1\wedge \operatorname{Xor}_{i=1}^n c_i\times \vec a_i=0$

即，其中的任意一个元素都不能通过其他元素选择一些进行组合得到。

构造异或线性基的步骤与线性基类似，具体的：

• 如果 $v=0$，那么代表 $v$ 与前面的元素线性相关，结束操作。
• 如果 $a_i$ 不存在，则 $a_i\gets v$，结束操作。
• 否则，令 $\vec v\gets \vec v\oplus \vec a_i$。

这个操作可以通过 bitset 进行优化，但是由于一般情况下 $\vec a_i$ 都是一个数的二进制为，所以位数很少，我们一般认为其复杂度为 $O(nm)$，其中 $m$ 是待处理元素的个数。