线性基学习笔记

写在前面

  • 本文是博主学习线性基时的笔记,主要参考了sengxianmenciljh2000的博客,并加入了一些本人的思考。转载请注明出处。

概念引入

  • 在线性代数中,$(basis)$是用来描述向量空间的基本工具。在$OI/ACM$中的题目中,利用基在异或空间中的特殊性质来解决问题,这类问题被称为线性基

预备知识

向量空间

  • 向量空间( vector space )$(F,V,+,\cdot )$,其中:$F$为域,$V$为集合,$V$中元素称为向量,$+$为向量加法,$\cdot $为标量乘法,且运算满足$8$条公理。

线性相关&线性无关

  • 对于向量空间中$V$上$n$个元素的向量组$(\vec{v_1}, \vec{v_2}, …, \vec{v_n})$,若存在不全为$0$的$n$个数$a_i \in F$,满足 $\sum_{i=1}^{n} a_i\vec {v_i} = a_1\vec {v_1}+a_2\vec{v_2}+\dots+a_n\vec{v_n}=\vec{0}$,则称这$n$个向量线性相关( linearly dependent ),否则称为线性无关( linearly independent )

线性组合

  • 线性组合( linear combination )即判断线性相关时的那个和式。换句话说,一组向量线性无关$\Leftrightarrow $其中任意向量都不能用其他向量的线性组合表示。

张成

  • 对于向量空间中$V$上$n$个元素的向量组$(\vec{v_1}, \vec{v_2}, …, \vec{v_n})$,其所有线性组合所构成的集合称为$(\vec{v_1}, \vec{v_2}, …, \vec{v_n})$的张成( span ),记为$span(\vec{v_1}, \vec{v_2}, …, \vec{v_n})$。

  • 若向量空间中$V$中的向量组$B$既线性无关,又可以张成$V$,则称为$V$的基( basis )。其中:$B$中元素称为基向量,若基中元素个数有限,则称该向量空间为有限向量空间,基元素个数为该向量空间的维度

性质

  • 若$B$是向量空间中$V$的基,则$B$具有以下性质:
    1. $B$是极小的能张成$V$的集合,它的任何真子集都不可能再是基;
    2. $V$中任意元素都可以唯一表示为$B$中若干元素的线性组合。

OI/ACM中的线性基

定义

  • 在$OI/ACM$中的线性基通常特指异或运算下的基,即:
    对于数$a_1, a_2, …, a_n$,把$a_i$表示成二进制${(b_m b_{m-1} … b_1)}_2$并看作一个向量$\vec{a_i}=(b_m,b_{m-1},…,b_1)$。由向量组$a_1,a_2,…,a_n$的张成,加上异或运算和乘法运算,便形成了一个向量空间$V=(\{0,1 \}, span(\vec{a_1},\vec{a_2},…,\vec{a_n}),\otimes,\cdot)$。下面我们要求的线性基就是这个向量空间$V$的基。
  • 为简化,我们称该集合为$S$,其中最大数在二进制下有$L$位,用一个$[0…L]$的数组$a$来储存线性基。

性质

  1. 线性基的异或集合中不存在$0$。
  2. 线性基的异或集合中每个元素的异或方案唯一。
  3. 线性基中每个数二进制最高位互不相同。
  4. 线性基的异或集合为$[1,2^L-1]$。
  5. 线性基矩阵的半三角性:
    • 若$a_i$的第$i$位为$0$,则只有满足$j>i$的$a_j$的第$i$位可能为$1$;
    • 若$a_i$的第$i$位为$1$,则$a_i$更高的二进制位都为$0$。

维护

插入

  • 逆序枚举$t$中所有为$1$的二进制位$j=L\rightarrow 0$:
    • 若$a_j \neq 0$,则令$t=t \otimes a_j$;
    • 若$a_j = 0$,则:
      • 枚举$k \in [0,j)$,若$t$的第$k$位为$1$,则令$t=t \otimes a_k$
      • 枚举$k \in (j,L]$,若$a_k$的第$j$位为$1$,则令$a_k=a_k \otimes t$
  • 令$a_j=t$,结束。
  • 时间复杂度:$\Theta (log\space t)$。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    struct LinearBasis {
    ll a[L + 1];
    LinearBasis() {
    std::fill(a, a + L + 1, 0);
    }
    void insert(ll t) {
    for (int j = L; j >= 0; j--) {
    if (!(t & (1ll << j))) continue;
    if (a[j]) t ^= a[j];
    else {
    for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k];
    for (int k = j + 1; k <= L; k++) if (a[k] & (1ll << j)) a[k] ^= t;
    a[j] = t;
    return;
    }
    }
    }
    };

合并

  • 两个线性基合并的过程就是将一个线性基暴力插入另一个线性基。
  • 代码如下:
    1
    2
    3
    void mergeFrom(const LinearBasis &other) {
    for (int i = 0; i <= L; i++) insert(other.a[i]);
    }

查询

  • 最大值: 即所有线性基的异或和。
  • 最小值: 即最低位的线性基。

例题

  1. SGU275 最大异或和

    • 题意:给定$n(1\leq n \leq 10^5)$个数,求它们的异或和最大是多少。
    • 分析:求出这$n$个数的线性基,答案是将所有线性基中所有数异或起来。
  2. HDU3949 子集$k$大异或和

    • 题意:给定$n(1\leq n \leq 10^4)$个数和$q(1\leq q \leq 10^4)$个询问$k$,每次求所有异或和中第$k$小的数。
    • 分析:根据线性基的性质,任意非空子集的异或和都不重复。假设线性基$m$个数中第$0…m$位为$1$的数依次为$(a_0,a_1,…,a_m)$,$k={(bxb{x-1}…b_0)}_2$,不难用二进制的思想证明最终结果为$\otimes_{0\leq i\leq x}b_i\cdot a_i$。
  3. BZOJ2115 最大路径异或和

    • 题意:给定$n(1\leq n \leq 50000)$个点$m(1\leq m \leq 10000)$条边的无向图,求一条从顶点$1$到$n$的路径(可重复经过点和边),使得路径上边权的异或和最大。
    • 分析:首先有一个常用技巧——任意一条$1$到$n$的路径的异或和,都可以由任意一条$1$到$n$的路径的异或和与图中一些环的异或和组合得到。然后通过$DFS$找到图中所有的环,和任意一条$1$到$n$的路径(异或值为$s$),我们的问题就变成了选择若干环,使得这些环的异或值与$s$异或起来最大。这就转化成了最大异或和问题。

总结

  • 大多情况下,在$OI/ACM$中有关异或运算求最值/求和的问题,一般都会用到线性基。如果给定很多数,我们通过构造它们的线性基,通过互相之间异或,生成原来所有数的异或和集合,从而大大减少判断的时间和次数。
  • 然后线性基和图论综合起来的话,常用的技巧就是:
    • 任意一条$1$到$n$的路径的异或和,都可以由任意一条$1$到$n$的路径的异或和与图中一些环的异或和组合得到。