Chlience

【算法】线性基学习指南
基本定义给定一个向量空间 $S$ , $S$ 的一组基 $B$ 是指在 $S$ 里面的可以线性生成 $S$ 的一个...
扫描右侧二维码阅读全文
24
2019/01

【算法】线性基学习指南

基本定义

给定一个向量空间 $S$ , $S$ 的一组基 $B$ 是指在 $S$ 里面的可以线性生成 $S$ 的一个线性无关子集,其中 $B$ 中的元素称为 基向量

换句话说,如果一个向量组 $B=\{e_1,e_2,\cdots,e_n\}$ 为 $S$ 的一组基,当且仅当:

  1. $B\subseteq S$
  2. $\forall v\in V,\exist(\lambda_1,\lambda_2,\cdots,\lambda_n)\in \mathbb{F^n}$ ,使得 $v=\lambda_1e_1,\lambda_2e_2,\cdots,\lambda_ne_n$
  3. $\forall (\lambda_1,\lambda_2,\cdots,\lambda_n)\in \mathbb{F^n}$ 如果 $\lambda_1e_1+\lambda_2e_2+\cdots+\lambda_ne_n=0$ ,则必然有 $\lambda_1=\lambda_2=\cdots=\lambda_n=0$

首先来解释下为啥
第一点: $B$ 为 $S$ 的真子集,这个没啥问题
第二点:其实这就是线性生成的定义,一个向量组 $B$ 能够生成的空间记为 $\text{span}(B)$,即 $B$ 的张成
第三点:这里保证 $B$ 中元素线性无关,若 $\lambda_1e_1+\lambda_2e_2+\cdots+\lambda_ne_n=0$ ,那么有 $-\lambda_1e_1=\lambda_2e_2+\cdots+\lambda_ne_n$ ,若 $\lambda_1\neq0$ ,必然有至少一个 $\lambda_i(i>1)\neq 0$ , $e_1$ 就可以被其他元素表示出来,即线性相关

性质

设 $B$ 是 $S$ 的子集。则 $B$ 是基,当且仅当满足了下列任一条件:

  • $S$ 是 $B$ 的极小生成集,就是说只有 $B$ 能生成 $S$ ,而它的任何真子集都不能生成全部的向量空间
  • $B$ 是 $S$ 中线性无关的极大集合,就是说 $B$ 在 $S$ 中是线性无关集合,而且 $V$ 中没有其他线性无关集合包含它作为真子集
  • $V$ 中所有的向量都可以按 唯一 的方式表达为 $B$ 中向量的线性组合。如果基是有序的,则在这个线性组合中的系数提供了这个向量关于这个基的坐标

一个向量空间中任意一组基的元素个数都相同,称其为向量空间的维度

OI中的定义

在 $OI$ 界,线性基常用来解决子集异或的问题
设 $S$ 为一无符号整数集,其子集 $T$ 的 异或和 组成的集合称之为 $\text{span}(S)$ ,即 $S$ 的张成

也就是说,我们将原来的加法运算变为异或运算,就是在 $OI$ 中的用法

构建方法

对于 $A=\{a_0,a_1,\cdots,a_n\}$ ,设它们二进制最高位为 $L$ ,那么可以将其看做 $n$ 个 $L$ 维向量
考虑求出 $S=\text{span}(A)$ 在异或意义下的基 $B$ ,显然 $B$ 中的元素应该为 $L$ 个

一开始,设 $B=A$ ,显然 $\text{span}(B)=S$
紧接着,每一次我们判断第 $i$ 个向量是否和前 $i-1$ 个向量线性无关,如果相关,去掉第 $i$ 个向量

如何判断当前向量能否被前面的向量张成?

考虑用前面的向量组成一个对角矩阵

每次加入一个新向量 $a$ ,我们从高到低检查它的每一位
若 $a_i=1$ ,尝试是否能够加入到第 $i$ 行(第 $i$ 行是否已经有元素)

如果不能,则异或第 $i$ 行的元素以消去第 $i$ 位,继续向后尝试
如果可以,则直接插入第 $i$ 行,然后用 $[i +1,n]$ 行的元素尽量将 $a$ 后面的 $1$ 消去,然后消去 $[1,i-1]$ 行元素的第 $i$ 位

Code

void calBasis() {
    for(int i = 1; i <= n; ++ i)
        for(int j = len; j ; -- j)
            if(a[i] & bin[j - 1]) {
                if(b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for(int k = 1; k < j; ++ k)
                        if(b[k] && (b[j] & bin[k - 1]))
                            b[j] ^= b[k];
                    for(int k = n; k > j; -- k)
                        if(b[k] & bin[j - 1])
                            b[k] ^= b[j];
                    break;
                }
            }
}
ll calMax(ll x) {
    for(int i = len; i >= 1; -- i)
        x = (x ^ b[i]) > x ? (x ^ b[i]) : x;
    return x;
}

Problem

Last modification:January 24th, 2019 at 03:56 pm

Leave a Comment