「算法笔记」线性基

线性基是一种特殊的基，它通常会在异或运算中出现。

定义

对于自然数集 $S$，$S$ 的线性基被定义为最小的集合 $R$，使得 $S$ 的任何一个子集的 $S’$，都能找到一个 $R$ 中的子集 $R’$，$S’$ 中所有元素的异或和等于 $R’$ 中元素的异或和，且对于 $R$ 的所有子集 $R’$，也能找到对应的 $S’$。

形象地说，$R$ 内元素随意异或得到的集合等于 $S$ 内元素随意异或得到的集合。

性质

线性基能相互异或得到原集合的所有相互异或得到的值。
线性基是满足性质 $1$ 的最小集合。
线性基内没有异或和为 $0$ 的子集（因为 $R$ 的空集的疑惑和为 $0$）。

线性组合

我们从另一个角度来考虑问题，即 $x$ 被表示为其他数的异或和代表什么。我们把 $x$ 拆成一个向量 $x=\{a_0,a_1,\dots,a_{k-1}\}$，$x=\sum{2^i\times a_i}$，其中 $k$ 是位数。

那么，$x$ 能被表示成 $S$ 的某个子集的异或和 转化为 $x$ 能被表示成 $S$ 中数所对应的向量在模 $2$ 意义下的线性组合。这样一来，$R$ 这个最的小能表示任何数的集合本质上就是 $S$ 的最大线性无关集合。

注意：这里的最小和最大并不矛盾，最小意味着线性无关，最大意味着能表示任何一个数。

现在，我们把数的异或，转换成了向量的线性组合。

求解

高斯消元时，如果某一行被前面的行消为 $0$，那么代表它可以被表示成前面向量的线性组合，这也就是为什么：

方程组有解、系数矩阵行列式不为 $0$、系数矩阵满秩、系数矩阵的线性无关集合大小为 $n$ ——这四个命题等价。

对于新加入的数 $x$，如果它能被表示成 $R$，就代表它能被 $R$ 消成 $0$。

我们把向量反过来写，把高位系数写在左边，低位系数写在右边，对所有数做高斯消元。最终矩阵会被消成一个上三角矩阵，剩下的不为 $0$ 的向量就是 $R$，而且每个向量（数）的最左边的非零数（最高位）都不相同。

因为矩阵行秩等于列秩，所以 $R$ 最多有 $k$（其中 $k$ 表示位数，一般为 $32$）个元素。

由于是在模 $2$ 的意义下，所以我们可以直接压位来做。记 $r_i$ 表示最高位为 $i$ 的线性基中的数。每次新加进来一个 $x$ 就从其最高位开始消去，如果某一位（假设为第 $i$ 位）无法消除了就把当前的 $x’$ 放进 $r_i$ 中，即 $x’$ 在线性基 $R$ 中。

代码

#include <cstdio>

const int N=1e6+5;
int n;
unsigned int a[N],r[32];

void Gauss(int n) {
    for(int i=1;i<=n;++i) {
        unsigned int x=a[i];
        for(int k=31;~k;--k) if(x&(1<<k)) {
            if(r[k]) x^=r[k];
            else {r[k]=x;break;}
        }
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%u",&a[i]);
    Gauss(n);
    for(int i=0;i<32;++i) if(r[i]) printf("%u\n",r[i]);
    return 0;
}

定义

性质

线性组合

求解

代码

习题