你说我一个连线性基都不会的人怎么可能走的远，我跟你说我也是这么想的，但是你先别急。
一、线性基
OI 中常用全部的就是 \(2\) 进制下的异或线性基。
线性基就是可以把一个集合里的数转化成一组基，使得这组基里所有 xor 出来的结果于原集合 xor 出来的结果完全一致。
这是一个线性基模板：
struct linear_basis_awa {
ll bs[64];
int cnt;
inline void init () {
for (int i = 0;i < 64; ++ i) bs[i] = 0;
cnt = 0;
}
inline void ins (ll x) {
if (!x) return ;
for (int i = 62;i >= 0; -- i) {
if (x & (1ll << i)) {
if (bs[i]) x ^= bs[i];
else {
cnt ++;
bs[i] = x;
break;
}
}
}
}
inline ll query_maxxor (ll x) {
ll res = x;
for (int i = 62;i >= 0; -- i) {
if ((res ^ bs[i]) > res) res ^= bs[i];
}
return res;
}
inline void merge_bas (linear_basis_awa O) {
for (int i = 0;i < 64; ++ i) ins (O.bs[i]);
}
inline void operator = (linear_basis_awa O) {
for (int i = 0;i < 64; ++ i) bs[i] = O.bs[i];
cnt = O.cnt;
}
};
其中这里的 \(bs_{w}\) 是最高位为 \(2^w\) 的基向量。
线性基的插入
如果 \(x\) 这个数内包含 \(2^w\) 这一位，如果基中已经有，那么直接异或掉 \(2^w\)，否则那就直接加入 \(x\)，然后结束，时间复杂度 \(O(\log w)\)。
线性基求最大 xor 和
对于 query_maxxor (int v) 函数的解释：查询 \(\displaystyle \max_{S \subseteq \text{base}} \left[\left(\bigoplus_{x \in S} x\right) \oplus v\right]\)；做法：贪心，如果 \(2^x\) 这一位异或下来是 \(1\)，那么一定要比后面所有位都是 \(1\) 产生的贡献之和（\(2^x - 1\)）还要大，所以我们从高位往低位贪心肯定是最优的，时间复杂度 \(O(\log w)\)。
线性基 xor 值计数
因为线性基里的数都是线性无关的，所以任意一个子集（不含 \(0\)）xor 出来的值都互不相同，如果含 \(0\) 总共就是 \(2^{cnt}\) 种情况，其中 \(cnt\) 是基中非 \(0\) 的数的数量。
线性基合并
直接将一个线性基里的数暴力插入到另一个线性基里即可，时间复杂度 \(O(\log^2 w)\)。