线性基入门

下面数学内容大概是氵长度，可以暂且跳过直接看线性基

前备知识

本文的前备知识：

什么是向量，懂得常用表示方法
了解什么是方程组
善用搜索引擎搜索自己需要的内容搜索亦是一门艺术

基

任何向量可由它所处的空间中的 基向量 线性组合表示，向量就是将基向量缩放并相加得到的。所以有了缩放和相加，就可以在基向量确定的空间构造任意向量。

比如二维空间的基向量通常被叫做 $\hat i$ 和 $\hat j$ ，那么对于向量 $\left[ \begin{array} { c } { - 2 } \\ { 3 } \end{array} \right]$ 就可以表示为 $-2\times \hat i +3\times \hat j$

采用数值描述一个向量时严格依赖于当前使用的基，对于向量 $\left[ \begin{array} { c } { x } \\ { y } \end{array} \right]$ 在不同基的情况下是不同的

线性组合

两个数乘向量的和，就可以被称作 线性组合

比如对于 $a \vec { v } + b \vec { w }$ 就是 $\vec { v }$ 和 $\vec { w }$ 的线性组合

下面来看一下为什么叫做线性组合

对于 $\vec { v }$ 和 $\vec { w }$ 的线性组合，我们现在固定 $b$ 的值，那么最后其线性组合所成向量的终点会在一条直线上（可以感性理解

向量的线性组合所成向量集合也叫做向量所张成的空间

对于两个向量 $\vec { v }$ 和 $\vec { w }$ 张成的空间

当 $\vec { v }$ 和 $\vec { w }$ 都为零向量时，其张成的空间为原点
当 $\vec { v }$ 和 $\vec { w }$ 共线，其张成的空间为 $\vec { v }$ 和 $\vec { w }$ 所在直线
当 $\vec { v }$ 和 $\vec { w }$ 不共线，其张成的空间为 $\vec { v }$ 和 $\vec { w }$ 所在平面

线性相关与线性无关

几何地来说，就是对于一组向量 $\{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\}$ 所张成的空间，若移除一个向量 $\vec {a_i}$ 其剩下的向量所张成的空间不变，那么这个向量对所张成的空间没有贡献（如两个共线的向量），就可以称这组向量是 线性相关 的，同时这个向量一定可以被表示为其他向量的线性组合

否则就称作这组向量 线性无关，也就是说其中任何向量 $\vec {a_i}$ 都不能被其他向量表示出来

硬核地来说，就是对于向量组 $\{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\}$ 与标量 $\{\lambda_1,\lambda_2,\cdots,\lambda_n\}$ 组成的式子 $\sum _ { i = 1 } ^ { n } \lambda _ { i } \vec { a } _ { i }$ ，当且仅当 $\lambda_1=\lambda_2=\cdots=\lambda_n=0$ 时，其值为 $0$ ，那么就可以说向量组 $\{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\}$ 线性无关，否则就说明其线性相关

证明：若存在 $\lambda _i\neq0$ 式子 $\sum _ { i = 1 } ^ { n } \lambda _ { i } \vec { a } _ { i }=0$ 成立，那么一定可以表示为 $\vec {a_k} = -{\sum _ { i = 1 ,i\neq k} ^ { n } \lambda _ { i }\vec { a } _ { i }\over \lambda_k}$ ，也就是 $\vec{a_k}$ 被我们表示成了其他向量，说明这组向量线性相关这证明貌似啥都没说

线性基

我们将一个数 $x$ 表示为二进制 $\overline {a_1a_2\cdots a_n}_{(2)}$ 我们分离各个位使它变为一个向量 $\vec v$

对于许多二进制数的集合 $\{b_1,b_2,\cdots,b_n\}$ 我们将其所有子集异或的结果也用上面方法分离为向量，其张成的向量空间叫做 $\text{V}$ ，那么 $\text{V}$ 就是一个域为 $\{0,1\}$ ，基本运算是异或的向量空间（下文中的异或用 $\oplus$ 表示，前面定义的向量的异或代表其对应二进制异或），而在信息学竞赛中讨论的线性基通常又被叫做 极大线性无关向量组

显然地 $\text{V}$ 作为向量空间是由基向量组成的，我们求出这些基，就能表示出 $\text{V}$ 的所有向量

现在考虑如何求出这些向量，这里给出一个较为简单的做法，首先考虑一个性质：

对于基中的两个向量 $\vec a$ 与 $\vec b$ ，令 $\vec c = \overrightarrow a \oplus \overrightarrow b$ ，则将 $\vec b$ 替换为 $\vec c$ ，其张成的空间不变

证明：证明很简单，当将 $\overrightarrow a_p$ 替换为 $\overrightarrow a_q' = \overrightarrow a_q \oplus \overrightarrow a_p,(p\neq q)$ 时，原来的 $\overrightarrow a_q = \overrightarrow a_q' \oplus \overrightarrow a_q$ ，于是前后的基是不变的

所以对于基里面的向量如何上述操作其所张成的空间总是不变的

现在构造一个线性基使其满足下面的性质

向量对应的二进制递增（即满足线性基中向量对应二进制的最高位递增）
向量对应的二进制最高位 两两不同（若相同，则通过对两个向量进行 $\oplus$ 来消去）

上述限定也就是让得到的线性基唯一，根据这个，就自然得到了一个插入一个向量（二进制数）的算法：

从高到低枚举当前数的二进制的非零位 $i$ ，若线性基中不存在第 $i$ 位为有值的，则插入到线性基中；若线性基中已经存在，则通过异或消去第 $i$ 位

这样，就得到了一个 $\text O(\log n)$ 的做法，下面给出 C++ 的代码实现

void insert (unsigned long long x) {
    for (int i = 62; i >= 0; i--)
        if (x & (1ll << i)) {
            if (base[i]) x ^= base[i];
            else {
                base[i] = x;
                break;
            }
        }
}

因为这个基的一些性质，OI 中提到的线性基一般都是通过这个方法得到的

对于两个向量空间，当然可以通过合并其基底来进行向量空间的合并。注意到由于向量空间是基向量的线性组合，故其向量空间的合并并非是两个空间的并，而是基向量的并的线性组合

由于笔者只会暴力合并，并不会更高级的合并方法，也并未在搜索引擎中有所收获，于是这里只给出暴力合并的方法

也就是对于两个线性基 $A = \{\overrightarrow { a _ { 1 } } , \overrightarrow { a _ { 2 } } , \cdots , \overrightarrow { a _ { n } }\}$ 与 $B = \{\overrightarrow { b _ { 1 } } , \overrightarrow { b _ { 2 } } , \cdots , \overrightarrow { b _ { n } }\}$ 每次取出 $B$ 中的每个向量 $\vec b_i$ 暴力插入 $A$ 中即可

void merge (unsigned long long *a, unsigned long long *b) {
    for (int i = 62; i >= 0; i--) {
        if (b[i]) insert(a, b[i]);
    }
}

求解最大异或和亦是线性基的一个应用，也就是对于一个集合 $T$ ，选出 $T$ 中的一个子集 $S$ ，满足 $\bigoplus _ {x\in S} x$ 最大，求出这个最大值「这不是sb题吗」

对于这个问题，直接贪心选取线性基中的元素即可

例题

给定一个边有边权的无向连通图，求出一条从 $1$ 号节点到 $N$ 号节点的路径，使得路径上经过的边的权值的 XOR 和最大（「WC2011」最大XOR和路径）

做法就是把所有环的长度插入线性基，然后随便找个链，在线性基中查询最大异或就好了

代码：

#define ul unsigned long long
#define int long long

const int N = 200000 + 10;
const int M = 400000 + 10;

ul base[N];
std::vector <std::pair <int, int> > e[N];

inline void add (int u, int v, int w) { e[u].pb(mp(v, w)); e[v].pb(mp(u, w)); }

void insert (ul x) {
    down (i, 60, 0)
        if (x & (1ll << i)) {
            if (base[i]) x ^= base[i];
            else {
                base[i] = x;
                break;
            }
        }
}

ul query (ul x) {
    down (i, 60, 0)
        if (x < (x ^ base[i])) x ^= base[i];
    return x;
}

int vis[N];
ul d[N];

void dfs (int u) {
    if (vis[u]) return;
    vis[u] = 1;
    for (auto i : e[u]) {
        if (vis[i.x]) insert(d[u] ^ d[i.x] ^ i.y);
        else d[i.x] = d[u] ^ i.y;
        dfs(i.x);
    }
}

signed main () {
    int n, m;
    n = read(); m = read();
    int u, v, w;
    up (i, 1, m) {
        u = read(); v = read(); w = read();
        add (u, v, w);
    }

    dfs(1);

    print(query(d[n]));
    return 0;
}

「线性基」线性基入门笔记

线性基入门

前备知识

基

线性组合

线性相关与线性无关

线性基

例题