Siyuan

「算法笔记」线性基
「算法笔记」线性基
扫描右侧二维码阅读全文
26
2019/01

「算法笔记」线性基

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


定义

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

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


性质

  1. 线性基能相互异或得到原集合的所有相互异或得到的值。
  2. 线性基是满足性质 $1​$ 的最小集合。
  3. 线性基内没有异或和为 $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$ 中。

时间复杂度:$\mathcal O(n \log w)$,其中 $w$ 为值域。


代码

#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 >> k) & 1) continue;
            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;
}

习题

发表评论