线性基

定义：给定一组向量，构成一个线性空间，如果我们能够找到一组线性无关的向量，使得这些向量的线性组合能够构成整个线性空间，则这一组向量成为该向量空间的线性基。

算法：计算线性基我们可以把一组向量排成矩阵，然后在矩阵上跑高斯消元法，消出来的非零行向量即为线性基，非零行向量数目为矩阵的行秩。

以下给出对于常规线性基的高斯消元代码：

void gauss() {
    int dim = 0; // 行秩
    for (int i = 1; i <= n; i++) {
        int piv = dim + 1;
        for (int j = dim + 1; j <= m; j++)
            if (abs(a[j][i]) > abs(a[piv][i]))
                piv = j;
        if (abs(a[piv][i]) < EPS) continue; // 自由元
        dim++;
        for (int j = 1; j <= n; j++)
            swap(a[dim][j], a[piv][j]);
        for (int j = 1; j <= m; j++) {
            if (j == dim) continue;
            if (abs(a[j][i]) < EPS) continue;
            double r = a[j][i] / a[dim][i];
            for (int k = 1; k <= n; k++)
                a[j][k] -= r * a[dim][k];
        }
    }
}

异或

简称 XOR，数学记号为 $$，C++ 中为 ^，异或本质上是在模 \(2\) 意义下的加法运算。因此线性代数的很多算法也可以应用到异或这样的有限域上，异或的一个很重要的性质是相消性，即一个数异或两次等于没异或！（等同于乘 \(2\)，在模 \(2\) 下就肯定没意义啦）。

异或的相消性很重要的一个应用是在图上使用 DFS 计算环上边的异或，我们只需要计算从 DFS 树根节点出发各个点到根上路径的异或和（记作 \(dis(u)\)）。如果我们在 DFS 上找到返祖边 \(e = (u, v)\)，环的异或就是 \(dis(u) \oplus dis(v) \oplus w(e)\)。我们可以看到这个运算中 \(u, v\) LCA 以上的部分都被抵消掉了，因此最后得到的就是整个环的异或和。如果求图上路径异或和的话我们可以用这样的方法搞出神奇的效果。

异或线性基

如何求出异或意义下的线性基呢？朴素的高斯消元肯定是可以的，但是对于异或我们首先可以压位减少常数，然后对于异或线性基我们还有一种求法，对于一个数 \(x\)，我们可以这样把 \(x\) 插入一组线性基：

1. 找到 \(x\) 的最高二进制位，记作 \(i\)。
2. 查看第 \(i\) 位的线性基 \(p[i]\) 是否被插入。
3. 如果没有被插入，插入第 \(i\) 位的线性基，结束。
4. 如果已经被插入了，令 \(x = x \oplus p[i]\)。

正确性证明：如果当前位没被插入则插入操作显然正确，如果被插入，则 \(x \oplus p[i]\) 不仅消除了第 \(i\) 位，同时可以证明如果 \(x \oplus p[i]\) 可以被线性基表出，则 \(x\) 一定也可以被线性基表出。

一个二进制数在被插入线性基的过程中如果失败了，那么它就会变成 \(0\)，暗示它可以由我们现有的线性基表出。

代码：

bool insert(int x) {
    for (int i = 30; i >= 0; i--) { // 最高位数
        if ((x >> i) & 1) {
            if (!p[i]) {
                p[i] = x;
                return true;
            } else
                x ^= p[i];
        }
    }
    return false;
}