异或空间线性基

定义

一堆数字能得到的非零异或和的结果，能被元素个数尽量少的集合得到

则这些元素的集合就是这一堆数字的异或空间线性基

如：1, 2, 3这三个数可以通过异或得到的非零值有1, 2, 3，同时这三个非零值可以通过1, 2这两个值异或得到，则这两个数的集合就是这三个数的异或空间线性基，同理2, 3这两个值也是一组线性基

我们只关心能否全部得到，且尽量的少，而不关心每种异或和的个数

构建基础

一堆数字中，任意的a和b，用\(a\oplus b\)的结果替代其中一个数字，不会影响非零异或和的组成

因为需要该数字时只需要异或这个结果再异或另一个数字就可以了
一堆数字中，任意的a和b，若有\(a\oplus b=0\)，则舍弃到其中一个数字，不会影响非零异或和的组成
一堆数字能否异或出0，需要单独标记

一般消元构建

取集合里的一堆数字，依次查看其二进制位，线性基的位数取决于这堆数字中二进制位最高1出现的位置

从高位往低位看，若最高位1对应的位数在线性基中的位置是空的，则可以直接放进去，否则与在该位置的数异或，消去最高位1，继续往后看位数，进行相同操作，直到空缺填入

时间复杂度：\(O(nm)\)，m为最大的二进制位数

Code

template<typename T>
class LinerBasis
{
public:
  LinerBasis(vector<T> &arr, T n): arr(arr), n(n)
  {
    basis.assign(BIT+1, 0);
    zero = false;
    compute();
  }
  void compute()
  {
    zero = false;
    for (int i = 1; i<=n; i++)
    {
      if (!insert(arr[i]))
      {
        zero = true;
      }
    }
  }

  bool insert(T num)
  {
    for (T i = BIT; i>=0; i--)
    {
      if ((num>>i)&1ll)
      {
        if (basis[i]==0)
        {
          basis[i] = num;
          return true;
        }
        num^=basis[i];
      }
    }
    return false;
  }

  bool haszero()
  {
    return zero;
  }

  vector<T> result()
  {
    return basis;
  }

private:  
  const int BIT = 60;
  vector<T> basis;
  vector<T> &arr;
  bool zero;
  T n;
};

应用

线性基大小：所有数字中最高位1的位置
异或和个数：线性基的大小已知n，则有\(2^n-1\)种
最大异或和：取线性基中的值异或当前值与当前值比较，取更大的
是否含0：查询标记

高斯消元构建

高斯消元可以得到标准形式的异或空间线性基，不需要主元与自由元的依赖关系

取数的二进制位，从最高位开始，将首个该位为1的数字与第一行的数字交换，然后该位其余有1的数让他们的1消失（与该位为0的数异或），依次往下进行，注意前面已经交换过的不需要再动

整个过程类似于矩阵消元成最简形

时间复杂度：\(O(nm)\)，m为最大的二进制位数

Code

template<typename T>
class LinerBasis
{
public:
  LinerBasis(vector<T> &arr, T n): basis(arr), n(n), len(0)
  {
    zero = false;
    compute();
  }
  void compute()
  {
    len = 1;
    for (int i = BIT; i>=0; i--)
    {
      for (int j = len; j<=n; j++)
      {
        if (basis[j]&(1ll<<i))
        {
          swap(basis[j], basis[len]);
          break;
        }
      }
      if (basis[len]&(1ll<<i))
      {
        for (int j = 1; j<=n; j++)
        {
          if (j!=len&&(basis[j]&(1ll<<i)))
          {
            basis[j] ^= basis[len];
          }
        }
        len++;
      }
    }
    len--;
    zero = (n!=len);
  }

  bool haszero()
  {
    return zero;
  }

  vector<T> result()
  {
    return basis;
  }

  T queryk(T k)
  {
    if (zero&&k==1) return 0;
    if (zero) k--;
    if (k>=(1ll<<len)) return -1;
    T ans = 0;
    for (int i = len, j = 0; i>=1; i--, j++)
    {
      ans^=basis[i];
    }
    return ans;
  }
  

private:  
  const int BIT = 60;
  vector<T> &basis;
  bool zero;
  T len;
  T n;
};

应用

前面所说的
求第k小的异或和

红魔咖啡馆

【数学】线性基

异或空间线性基

定义

构建基础

一般消元构建

Code

应用

高斯消元构建

Code

应用