你说我一个连线性基都不会的人怎么可能走的远，我跟你说我也是这么想的，但是你先别急。

一、线性基

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)\)。