专栏文章

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

旻旻偲奶香起司喵
算法·理论参与者 8已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@miqqoxn3
此快照首次捕获于
2025/12/04 09:10
3 个月前
此快照最后确认于
2025/12/04 09:10
3 个月前
查看原文

线性基学习笔记

目录：

  1. 线性基概念。
  2. 线性基性质。
  3. 普通消元求线性基。
  4. 高斯消元求线性基。
  5. 线性基应用。
  6. 一些例题。

线性基概念

我们常说的线性基指的是异或空间线性基。
什么是异或空间？你现在有一个数集 AA ，由 AA 的子集的非 00 异或和，组成的集合就叫做异或空间。
eg： A={1,2,3}A = \{1,2,3\}，他的一些子集有 {1}\{1\} 异或和为 11，{2}\{2\} 异或和为 22，{2,1}\{2,1\} 异或和为 33。这些子集的异或和都放进一个集合就成了异或空间，所以 AA 异或空间就是 {1,2,3}\{1,2,3\}。
什么是线性基？我们希望用一个元素尽可能少的集合，也能表示出这个这个异或空间，那么这个元素尽可能少的集合，就是一组关于这个异或空间的线性基。
我们可以将一组线性基看作是二进制下的一组数组，他每一位如果有数的话，那么这个数的最高二进制位一定是当前二进制位，可以将每一位上的数称作一位基。
注意： 我们只关心非 00 异或和，同时对于一个异或空间，他可能有多组线性基。

线性基性质

  1. 对于一个数集 AA ，若其中有元素 aa 和 bb ,可以用 a⨁b a \bigoplus b 代替 aa 或 bb (a=a⨁b⨁ba = a \bigoplus b \bigoplus b ，多异或一次而已)。
    同理，当 ⨁iai=⨁jbj\displaystyle \bigoplus_i a_i = \bigoplus_j b_j 时，可以用左边的一系列数代替右边。
  2. 对于一个数集 AA ，若有元素 aa 和 bb ，使得 a⨁b=0a \bigoplus b = 0 ，则我们可以舍去 aa ，bb 中任意一个（a==ba == b)。

普通消元求线性基

我们现在有一个序列 aa ，我们要求其异或空间线性基。
考虑将 aia_i 分别插入线性基。先将 aia_i 进行二进制分解。找到二进制下，最高位的那个 11 。
若此时这一位还没有基，那么就把这一位的基设为 aia_i ，否则就将 aia_i 与这一位的基异或，去找下一位 11 重复此操作。
直到 aia_i 变为 00 或者找到一位没有值的基插入。
CPP
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}a = \{12,9,14,11\}
​ i=1i = 1 时，basis0=basis1=basis2=basis3=0basis_0 = basis_1 = basis_2 = basis_3 = 0，此时没有一位基有值。
​ 考虑插入 a1a_1 二进制分解为 11001100 最高位 11 是第三位。第三位的基没有值，于是 basis3=a1=12basis_3 = a_1 = 12 剩下基没有改变。
​ i=2i = 2 时，basis0=basis1=basis2=0,basis3=12basis_0 = basis_1 = basis_2 = 0,basis_3 = 12
​ 考虑插入 a2a_2 二进制分解为 10011001 最高位 11 是第三位。此时第三位的基是 1212 于是 99 与 1212 异或得 (0101)2=(5)10(0101)_2 = (5)_{10} 。
​ 找到下一位的 11 是第 22 位。第二位的基没有值，所以 basis2=5basis_2 = 5。
​ 以此类推。
为什么可以这样呢？
我们要让线性基的元素尽可能少，那么我们最佳的方式就是每一位只有一个值，所以我们保证每一位的基的值对应的最高位的 11 就是此位。同时根据性质 11 我们用两者异或的结果去替代原来的数，并不会改变线性基的合理性。

高斯消元求线性基

高斯消元求出来的线性基和普通消元求出来的线性基不同的地方在于，高斯消元求出来的线性基是标准形式的线性基。
什么是标准形式？就是对于求出来的线性基，二进制下，每一位对应着只有一个 11 并不会出现同一位多个 11 情况。
而在普通消元中，我们因为只找最高位的 11 所以我们无法保证他的低位的 11 和其他基的低位的 11 没有重合。
高斯消元求线性基的过程类似于，高斯消元解线性方程组。
类似解线性方程组。假设当前要算出第 ii 位的基。从第 ii 行往下找，找到第一个 aja_j ，使得他的该二进制位为 11 ，将 aia_i 与 aja_j 交换。
然后再次遍历 a1a_1 到 ana_n 若 aja_j 这位也是 11 则将 aja_j 与 a1a_1 异或，来保证这一位，只能出现 aia_i 一个 11。eg ：
先确定第五位的基，从 a1a_1 开始找，发现 a2a_2 第五位是 11, 于是将 a1a_1 与 a2a_2 交换。得下图：
然后我们又再次遍历 aa 发现 a3a_3 与 a4a_4 第五位也有 11，于是将 a3⨁a1,a4⨁a1a_3 \bigoplus a_1,a_4 \bigoplus a_1。又得下图：
以此类推，最后第 ii 的 22 进制的和就是第 ii 的基。
CPP
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×log⁡V)O(n \times \log V) 其中 VV 是值域。
线性基的大小为 log⁡V\log V 只和每个数在二进制下最多能拆成多少位有关。

线性基的一些应用。

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

一些例题

P3812 ：求异或空间最大值板子题。
P3857 ：求异或空间大小板子题。
P4570 ：
一个很常见的思想，贪心地规定我们插入线性基的顺序。
因为线性基并不会因为插入顺序的改变，而导致最后得到的线性基对应的线性空间不同，所以我们可以随意地排序插入顺序。
所以这个题我们可以按照魔力价值排序，然后插入线性基，若一个数可以插入线性基，即他改变了某一位基的值，我们就将他的魔力值计入答案。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...