本来想多找点例题的，但是发现好像不是很有空。之前随手打的，先发上来好了。

这篇文章参考于B站视频 CSU-ICPC集训课程 线性基。

CCPC网络赛遇到一道题，说是要用到线性基。遂记录一下。

线性基的定义

线性基是一个集合。

从原集合中选取任意多个数异或得到的值都能通过在线性基中选取一些数异或得到。

也就是说线性基是对原集合的压缩。

线性基的模版题就是在一些数中取任意个数，要求异或值最大是多少。

例子引入

对于

集合$A={a_{1},a_{2},\dots a_{i-1},a_{i},a_{i+1},\dots a_{j} \dots a_{n} }$，将其中的$a_{i}$用$a_{i} \oplus a_{j} (j \in [1,n] \cap j\neq i )$ 替换得到
集合$B={a_{1},a_{2},\dots a_{i-1},a_{i} \oplus a_{j},a_{i+1},\dots a_{j} \dots a_{n} }$

从集合A中选取任意多个数异或得到的值都能在集合B中选取一些数进行异或得到。

这一点应该是挺显然的。具体地讲，假如说需要单独的$a_{i}$的话，在B中挑出$a_{i} \oplus a_{j}$ 与$a_{j}$。如果两个都需要的话只取B中的$a_{i} \oplus a_{j}$即可。

那么很显然，这样的操作进行一次和进行多次都是可以的。

具体的例子

一个集合有如下几个数（二进制下）

$$
\begin{aligned}
a_{1}=10011\\a_{2}=10010\\a_{3}=00010
\end{aligned}
\Rightarrow_{a_{2}=a_{2}\oplus a_{1}}
\begin{aligned}
a_{1}=10011\\a_{2}=00001\\a_{3}=00010
\end{aligned}
$$

可以发现上面一次操作之后，用某一位作为最高位的数唯一。（这个性质就是帮助我们压缩集合的。）

那么，当我们往这个集合中插入一个元素$a$时（假设最高位为第$i$位），只需要查看该集合中是否存在最高位为第$i$位的数字。

如果不存在，那么直接插入该集合即可。
如果存在，假设该数为$b$，则令$a=a\oplus b$，重复从上面判断存不存在开始进行操作，直到最后$a=0$（即表示线性基里的所有元素已经可以表示初始的$a$）。

这样子的话显然插入操作的时间复杂度是$O(\log_{2}a)$。

那么不管插入多少个数（或者说原集合有多少个数），都可以按照上述的方法把它压缩成元素个数为$(\log_{2}值域)$的集合。

模板题

题意

在$n$个数中取任意个数，问异或起来的和最大是多少。

解法

线性基里，用某一位作为最高位的数唯一。

那么我们直接贪心的从高位到低位考虑要不要选即可。