算法学习笔记(12): 线性基

线性基

熟练掌握异或运算是食用本文的大前提，请读者留意

是什么？

是一种利用线性代数的知识，用于解决异或问题的一种手段（不能算作数据结构吧这）

本文并不会涉及到线性代数。而是从OI基础算法思想的角度阐释线性基。尽管这可能违背了设计该方法的初衷。

一般来说，预处理的时间复杂度为 \(O(kn)\) 其中 \(k\) 一般为 \(31 \sim 32\)，也就是 \(log_2max\)。单次操作一般也是 \(O(k)\) 的复杂度。

xxj 是一个数组，至于为什么去这个名字……

令 xxj[i] 表示最高为 1 的位 i 的一个异或和（如果有的话）。

我们只需要维护这么 \(k\) 个数就行了

我们可以这么理解，0100 可以由 0101 和 0001 异或和起来，那么我们只需要维护 0101 和 0001 即可。

考虑如何新增一个数 x 进去？

由于我们维护的是异或和，那么对于 xxj 内的任何元素都可以异或上 x 以保证至多只有 \(k\) 个数。

假设 x 最高为 1 的位为 i，如果 xxj[i] 已经存在了一个数，那么我们将 x 异或上 xxj[i]，重复上述步骤，否则，就令 xxj[i] = x。

如果，最终 x 变成了 0，那么证明，用之前存在的数可以凑出 x，否则，不可以。

其实，这既是维护基的方法，也是判断某个数是否可以被异或出来的方法……

这里，我们利用贪心的思想，先找到xxj内最大的数，也就是最高为 1 的为最高的那个数。

很明显，如果 i < j 那么 xxj[i] < xxj[j]。

假如我们找到了 xxj[i]，令 res = xxj[i]，然后逆序 j 枚举 [0, i)，如果，res 的第 j 位不为 1，那么res ^= xxj[j]。

但是……我们的实现肯定不能如此复杂，那么就考虑贪心，如果 j 位为变为了 1，那么之后的所有位都变为 1 做出的贡献都没有这个位做出的贡献大，那么我们优先保证最高位为1即可。

int qmax() {
    int ans = 0;
    for (int i = 30; i >= 0; --i) {
    	ans = max(ans, ans ^ xxj[i]);
    }
    return ans;
 }

解释了跟没解释一样……

暂时没时间写了，候补