线性基入门

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

前备知识

本文的前备知识:

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

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

比如二维空间的基向量通常被叫做 ,那么对于向量 就可以表示为

采用数值描述一个向量时严格依赖于当前使用的基,对于向量 在不同基的情况下是不同的

线性组合

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

比如对于 就是 的线性组合

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

对于 的线性组合,我们现在固定 的值,那么最后其线性组合所成向量的终点会在一条直线上(可以感性理解

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

对于两个向量 张成的空间

  • 都为零向量时,其张成的空间为原点

  • 共线,其张成的空间为 所在直线

  • 不共线,其张成的空间为 所在平面

线性相关与线性无关

几何地来说,就是对于一组向量 所张成的空间,若移除一个向量 其剩下的向量所张成的空间不变,那么这个向量对所张成的空间没有贡献(如两个共线的向量),就可以称这组向量是 线性相关 的,同时这个向量一定可以被表示为其他向量的线性组合

否则就称作这组向量 线性无关,也就是说其中任何向量 都不能被其他向量表示出来

硬核地来说,就是对于向量组 与标量 组成的式子 ,当且仅当 时,其值为 ,那么就可以说向量组 线性无关,否则就说明其线性相关

证明:若存在 式子 成立,那么一定可以表示为 ,也就是 被我们表示成了其他向量,说明这组向量线性相关 这证明貌似啥都没说

线性基

我们将一个数 表示为二进制 我们分离各个位使它变为一个向量

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

显然地 作为向量空间是由基向量组成的,我们求出这些基,就能表示出 的所有向量

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

对于基中的两个向量 ,令 , 则将 替换为 ,其张成的空间不变

证明:证明很简单,当将 替换为 时,原来的,于是前后的基是不变的

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

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

  1. 向量对应的二进制 递增(即满足线性基中向量对应二进制的最高位递增)
  2. 向量对应的二进制最高位 两两不同(若相同,则通过对两个向量进行 来消去)

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

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

这样,就得到了一个 的做法,下面给出 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 中提到的线性基一般都是通过这个方法得到的


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

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

也就是对于两个线性基 每次取出 中的每个向量 暴力插入 中即可

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

求解最大异或和亦是线性基的一个应用,也就是对于一个集合 ,选出 中的一个子集 ,满足 最大,求出这个最大值 「这不是sb题吗」

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

例题

给定一个边有边权的无向连通图,求出一条从 号节点到 号节点的路径,使得路径上经过的边的权值的 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;
}