线性基学习笔记及其相关证明

线性空间

线性基所在线性空间中元素均为非负整数且元素间运算为异或。

线性基

性质

线性基是特殊线性空间中的一组基底，具有以下特殊性质：

0：若\(d_i > 0\)，则\(d_i\)二进制下第\(i+1\)位为\(1\)且\(i+1\)位为最高位。

1：元素线性无关，即异或和非0

证明：线性相关时不再被插入。

2：其所在线性空间中的每个元素能唯一被此线性基表示，同时原序列每个元素可被表示。

证明：前者为线性无关，后者为异或路径上的元素及插入点构成成\(A_i\)

3：选取一些元素构成集合\(S\)，其异或和\(x\)代替\(S\)中任意元素后新\(S\)和其他线性基中的元素张成的空间不变。

证明：考虑\(T\subset S,T\neq \empty,\bigoplus_{i=1}^{\vert T\vert}d_i=x\)时，对于\(\forall i,d_i\in T\)有\(\bigoplus_{j=1}^{i-1}d_j\bigoplus_{j=i+1}^{\vert T\vert}\oplus x=d_i\)，易得其等价。

4：线性基中数的个数唯一，且最少。

证明：对于一个不能插入的原序列数\(x，(T\subset S,x=\bigoplus_{_i=1}^{\vert T\vert }d_i)\)和线性基\(S\)，交换满足\(\forall i,i\in T\)的\(d_i\)与\(x\)，性质在任意时刻仍然成立。

构造

假设已经拥有一个线性基，想要插入一个数\(x\)

从高位往低位考虑，如果\(x\)的第\(j\)位为\(1\)且\(d_i>0\)那么\(x=x\oplus d_i\)，即消掉与\(d_i\)相同的位且对其他\(i\)位取反。

异或保证了线性无关，明显若中途为\(0\)，则线性相关，停止插入。

如果\(d_i=0\)且\(x\)的\(i+1\)位为\(1\)，则插入到\(d_i\)中

明显对于\(j>i，d_j>0\)的\(d_j\)的第\(i+1\)位亦可能为\(1\)，但一定有\(j+1\)位为\(1\)，因此插入后满足线性无关。

代码

void insert(LL x) {
  for (LL i = 55; i >= 0; i--) {
    if ((x >> i) & 1LL) {
      if (!d[i]) {
        d[i] = x;
        break;
      } else x ^= d[i];
    } else if (!x) return;
  }
}

应用

1：最大最小异或和。

sol：\(d_i\)的最高位为\(i+1\)位，直接贪心即可

2：\(k\)小异或和。

sol：考虑构造新线性基，保证对于\(\forall i, d_i>0\)时，仅\(d_i\)的\(i+1\)位为\(1\)。

正确性：对于\(\forall i, d_i>0\)的 \(d_i\),若第\(\forall j, j\in[i-1,0]\)位\(>0\)且\(d_{j-1}=0\)，那么仅可能存在

\(\forall k,k\in[i-1,j+1]\)的\(d_k(d_k>0)\)使得\(d_k\)的第\(j\)为\(1\)，能够消去\(d_i\)的第\(j\)位，但此时若\(d_i\)的\(k+1\)位为\(0\)

明显\(d_i\)将在异或后变大，即不符合变小的约定。

若\(d_i\)的\(k+1\)位为\(1\)，则符合约定，因此构造满足上述性质的线性基一定会使得独立时能异或出\(k\)小。

\(k\)小异或和构造方法

对于每一个\(d_i\)考虑其\(1\)至\(i\)位，若\(d_i\)的\(j\)位为\(1\)，将其异或上\(d_{j-1}\)即可构造出目标线性基。

正确性：考虑前\(i-1\)位已经构造出来了，构造第\(i\)位的时候也一定合法

这启发我们对于一组数插入的顺序影响基底，但是不影响其张成的空间，这也对应着性质4

线性基学习笔记及其相关证明

原文：https://www.cnblogs.com/cjc030205/p/11638094.html