$介绍$
线性基通常用来解决异或类问题，
对于 $n$ 个数 $a_1, a_2, a_3, … , a_n (1\leq a_i\leq V)$，假设 $S = \{ \oplus_{x\in T} a_x \mid T \subseteq \{1, 2, …, n\}\}$，也就是从这 $n$ 个数中选出若干个异或起来能得到的数的集合。
那么它的线性基就是包含 $O(\log V)$ 个数的集合，设 $S’$ 表示从中选出若干个数异或起来得到的数的集合，那么满足 $S’ = S$。
$构造$
若现在给定 $n$ 个数 $a_1, a_2, a_3, … , a_n$ ，那么如何构造出它的一组线性基呢？
一组线性基可以表示为 $T = \{ t_1, t_2, … , t_{\log V} \}$，其中的每一位要么为 $0$，要么为二进制下最高位为 $i$ 的数。
空集的线性基为 $T = {0}$。
如果我们已知 $a_1, a_2, a_3, … , a_{n - 1}$ 的线性基 $t$，那么加入 $a_n$ 至线性基的流程如下
function insert(x:integer)
for i := 30 downto 0 do
if t[i] > 0 then
x := x ^ t[i]
else
{
t[i] := x
break
}
end function
要证明 $T$ 是 $a_1, a_2, a_3, … , a_n$ 的线性基，只需两点：
- $a$ 中的每一个数都能由 $T$ 中若干个数异或得到
- $T$ 中的每一个数都能由 $a$ 中若干个数异或得到
首先 $T$ 和加入 $a_n$ 之前的 $T’$ 相比相当于在原先为 $0$ 的位置上加了某个数 $x$ 或不变。
既然 $a_i(1 \leq i < n)$ 能由于 $T’$ 中若干数异或得到，同样能由 $T$ 中若干个数异或得到。
然后考虑 $a_n$ 是否能由 $T$ 得到，根据插入操作的伪代码，显然是可以得到的。
接下来考虑 $T$ 中的数是否都能由 $a$ 中若干个数异或得到，同理只要考虑新加入的数 $x$，
$x$ 可以表示为 $a_n$ 异或上若干个 $t_i$，而这若干个 $t_i$， 每一个都一定可以被 $a_1, a_2, … , a_{n - 1}$ 中的数异或得到，故 $T$ 一定为 $a_1, a_2, … , a_n$ 的线性基。
单次加入的时间复杂度 $O(\log V)$。
$查询最大值$
在一个集合能选出任意个数，使得异或起来后和给定的 $v$ 再异或的值最大，求这个最大值。
由于线性基满足 $t_i$ 上的数要么为 $0$，要么为二进制下最高位为 $i$ 的数，所以贪心从高位到低位取。
时间复杂度 $O(\log V)$
int qry(int x) {
for (int i = 30; i >= 0; i -- )
if (!(x >> i & 1)) {
x ^= a[i];
}
return x;
}
$合并$
暴力的将一个线性基里的数加入到另一个线性基，时间复杂度 $O(\log^2 V)$
LineBase merge(LineBase A, LineBase B) {
for (int i = 30; i >= 0; i -- )
if (B.a[i]) A.add(B.a[i]);
return A;
}
$性质$
1.如果现在给你一个线性基，将其中一个数变为与线性基内另一个下标小于它的元素的异或和，那么就得到了一个不同的满足要求的线性基。
2.如果将线性基进行如下操作
function exchange(x:integer)
for i := 30 downto 0 do
for j := i - 1 downto 0 do
if t[i] & (1 << j) then
t[i] := t[i] ^ t[j]
end function
那么就可以得到一个线性基，满足其中任意两个数的与运算均为 $0$。
3.每一个可以由异或得到的数 $v$ 出现次数均为 $2^{n-len} (len 为线性基长度)$
证明：由于 $n$ 个数取若干个可以得到的不同的数是固定的，所以线性基长度是固定的。
称 $a_1, a_2, … , a_n$ 中的数在线性基中，当且仅当在加入它时执行了赋值操作。
所以 $a$ 中有 $len$ 个数在线性基中，观察这 $len$ 个数，发现将它们组合在一起同样可以组成一个线性基。
在剩下的 $n - len$ 个数中随便选，并且异或起来得到 $2^{n-len}$ 个数，设得到了 $x$，那么对于每一个 $v$，在存在于线性基中的 $len$ 个数一定可以有异或和为 $v \oplus x$ 的若干个数，所以对于每一个 $v$，都有 $2^{n-len}$ 种选择，证毕。
$求第 k 小异或值$
注意这里的第 $k$ 小指的是不重的第 $k$ 小。
先由性质 $2$ 改造线性基，再把为 $0$ 的位去掉。
于是如果 $k = (11100010)$，那么就是求 $base_1 \oplus base_5 \oplus base_6 \oplus base_7$，对应位异或起来即可。
int get_rk(int x) {
vector<int> v;
for (int i = 0; i < 31; i ++ ) //改造线性基
if (a[i] > 0)
v.push_back(i);
int res = 0;
for (int i = 0; i < v.size(); i ++ )
if (x >> v[i] & 1)
res += 1 << i;
return res;
}
