线性基入门

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

前备知识

本文的前备知识：

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

基

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

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

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

线性组合

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

比如对于 就是 和 的线性组合

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

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

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

对于两个向量 和 张成的空间

• 当 和 都为零向量时，其张成的空间为原点

• 当 和 共线，其张成的空间为 和 所在直线

• 当 和 不共线，其张成的空间为 和 所在平面

线性相关与线性无关

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

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

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

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

线性基

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

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

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

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

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

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

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

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

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;
}