线性基（左程云）学习笔记

旻偲 · 2024-12-18 22:54:32 · 算法·理论

线性基学习笔记

线性基概念

我们常说的线性基指的是异或空间线性基。

什么是异或空间？你现在有一个数集 A ，由 A 的子集的非 0 异或和，组成的集合就叫做异或空间。

eg： A = \{1,2,3\}，他的一些子集有 \{1\} 异或和为 1，\{2\} 异或和为 2，\{2,1\} 异或和为 3。这些子集的异或和都放进一个集合就成了异或空间，所以 A 异或空间就是 \{1,2,3\}。

什么是线性基？我们希望用一个元素尽可能少的集合，也能表示出这个这个异或空间，那么这个元素尽可能少的集合，就是一组关于这个异或空间的线性基。

我们可以将一组线性基看作是二进制下的一组数组，他每一位如果有数的话，那么这个数的最高二进制位一定是当前二进制位，可以将每一位上的数称作一位基。

注意：我们只关心非 0 异或和，同时对于一个异或空间，他可能有多组线性基。

线性基性质

对于一个数集 A ，若其中有元素 a 和 b ,可以用 a \bigoplus b 代替 a 或 b (a = a \bigoplus b \bigoplus b ，多异或一次而已)。

同理，当 \displaystyle \bigoplus_i a_i = \bigoplus_j b_j 时，可以用左边的一系列数代替右边。
对于一个数集 A ，若有元素 a 和 b ，使得 a \bigoplus b = 0 ，则我们可以舍去 a ，b 中任意一个（a == b)。

普通消元求线性基

我们现在有一个序列 a ，我们要求其异或空间线性基。

考虑将 a_i 分别插入线性基。先将 a_i 进行二进制分解。找到二进制下，最高位的那个 1 。

若此时这一位还没有基，那么就把这一位的基设为 a_i ，否则就将 a_i 与这一位的基异或，去找下一位 1 重复此操作。

直到 a_i 变为 0 或者找到一位没有值的基插入。

void insert(int x)
{
    for(int i = 60;i >= 0;i--)//从高位往低位枚举。
    {
        bool use = ((1ll << i) & x);//看当前位是什么
        if(use)//是1
        {
            if(!basis[i]) //如果这一位的基没有值
            {
                basis[i] = x;
                return;
            }
            x ^= basis[i];//有值，进行异或，去找下一位。
        }
    }
}

eg ： a = \{12,9,14,11\}

i = 1 时，basis_0 = basis_1 = basis_2 = basis_3 = 0，此时没有一位基有值。

考虑插入 a_1 二进制分解为 1100 最高位 1 是第三位。第三位的基没有值，于是 basis_3 = a_1 = 12 剩下基没有改变。

i = 2 时，basis_0 = basis_1 = basis_2 = 0,basis_3 = 12

考虑插入 a_2 二进制分解为 1001 最高位 1 是第三位。此时第三位的基是 12 于是 9 与 12 异或得 (0101)_2 = (5)_{10} 。

找到下一位的 1 是第 2 位。第二位的基没有值，所以 basis_2 = 5。

以此类推。

为什么可以这样呢？

我们要让线性基的元素尽可能少，那么我们最佳的方式就是每一位只有一个值，所以我们保证每一位的基的值对应的最高位的 1 就是此位。同时根据性质 1 我们用两者异或的结果去替代原来的数，并不会改变线性基的合理性。

高斯消元求线性基

高斯消元求出来的线性基和普通消元求出来的线性基不同的地方在于，高斯消元求出来的线性基是标准形式的线性基。

什么是标准形式？就是对于求出来的线性基，二进制下，每一位对应着只有一个 1 并不会出现同一位多个 1 情况。

而在普通消元中，我们因为只找最高位的 1 所以我们无法保证他的低位的 1 和其他基的低位的 1 没有重合。

高斯消元求线性基的过程类似于，高斯消元解线性方程组。

类似解线性方程组。假设当前要算出第 i 位的基。从第 i 行往下找，找到第一个 a_j ，使得他的该二进制位为 1 ，将 a_i 与 a_j 交换。

然后再次遍历 a_1 到 a_n 若 a_j 这位也是 1 则将 a_j 与 a_1 异或，来保证这一位，只能出现 a_i 一个 1。eg ：

先确定第五位的基，从 a_1 开始找，发现 a_2 第五位是 1, 于是将 a_1 与 a_2 交换。得下图：

然后我们又再次遍历 a 发现 a_3 与 a_4 第五位也有 1，于是将 a_3 \bigoplus a_1,a_4 \bigoplus a_1。又得下图：

以此类推，最后第 i 的 2 进制的和就是第 i 的基。

int len = 1;// 有多少位基
for(int i = BIT;i >= 0;i--)//从高位往低位枚举，BIT是最高多少位
{
    for(int j = len;j <= n;j++)//找第一个该位是1的
    {
        if(a[j] & (1ll << i)) //找到了
        {
            swap(a[j],a[len]);//将第len位和第j位交换。
            break;
        }
    }
    if(a[len] & (1ll << i))//说明找到了一个合法的该位是1的数
    {
        for(int j = 1;j <= n;j++)
        {
            if(j != len && (a[j] & (1ll << i))) a[j] ^= a[len];//去把其他的该位是1的数消掉。
        }
        len++;//说明多了一位基。
    }
}

普通消元和高斯消元的时间复杂度都是 O(n \times \log V) 其中 V 是值域。

线性基的大小为 \log V 只和每个数在二进制下最多能拆成多少位有关。

线性基的一些应用。

求异或空间中的最大值。
- 从高位往低位枚举。维护当前最大值 maxx ，若当前基是 basis_i ，则有 maxx = \max \{maxx,maxx \bigoplus basis_i\} 。
求异或空间中第 k 小。（只能用高斯消元法求出的标准形式的线性基来做）
- 很美妙的性质，将 k 二进制分解，即 \sum_{i = 0}^{60} 2^i \times 0/1 = k ，若第 i 位是 1 ，则将第 i 的基异或进答案。
已知线性基大小求异或空间大小。
- 若有 k 位基，则异或空间的大小为 2^k - 1 （不包含 0 )，如果可能出现 0 则在求线性基的时候判断一下该组线性基是否有 0 即可。

一些例题

P3812 ：求异或空间最大值板子题。

P3857 ：求异或空间大小板子题。

P4570 ：

一个很常见的思想，贪心地规定我们插入线性基的顺序。

因为线性基并不会因为插入顺序的改变，而导致最后得到的线性基对应的线性空间不同，所以我们可以随意地排序插入顺序。

所以这个题我们可以按照魔力价值排序，然后插入线性基，若一个数可以插入线性基，即他改变了某一位基的值，我们就将他的魔力值计入答案。