基本概念

线性基可以解决向量方面的问题，具体来说，它可以为一个向量空间确立一些基底，这些基底通过数乘运算可以表示向量空间中的所有向量

对于一个异或线性基，数乘运算之后，只有两种情况 ，以及其本身，因此看上去就是基底选或者不选

线性基的底层原理是高斯消元法，算法本质上在用代码模拟这个过程

成为基底的核心条件是“具备无法被组合的独立属性”，而它在阶梯矩阵中的最终座次，严格取决于消元后残存的最高维度的非零属性。

用高斯消元法构建线性基，本质上是一个从高维向低维逐层扫描的“沉淀”过程：

拿着一个新向量，从最高维开始向下俯视。如果它在当前维度的属性不为 ，就面临两种判定：

遇阻则消：如果该维度已被老基底占据，就用老基底对其进行消元（抹掉当前维度的属性），让向量继续向更低维跌落。 遇空则入：如果该维度是空位，当前向量就立刻在此“入座”，成为该维度的专属基底。

这个过程最精妙的严谨性在于：当向量落入某一层空位时，我们可以百分之百确信，它比当前维度更高的所有属性，都已经在之前的层层下落中被老基底彻底消去了。因此，当前的空缺维度，就是它理所应当的最高专属座次。

生成线性基有两种方法，贪心法和高斯消元法，贪心法的本质也是高斯消元，不过生成的基底不够纯净（更高位中有可能存在对应位的 ），无法查询第 大的数

可以对已有线性基进行重构，或者插入数字前先用低位基底消去数字的低位 让基底保持纯净

图论与线性基

例题 :

1. 洛谷P4151 [WC2011] 最大 XOR 和路径
2. CF724G Xor-matic Number of the Graph

例题1

这是一道经典的“线性基+图论”板子题：求无向连通图中，起点到终点异或和最大的路径。

解题的核心是路径抽象：任意一条复杂路径的异或和 = 一条简单路径的异或和 若干个环的异或和。

为什么可以这样等价？

因为异或运算满足 。如果为了去绕某个环而走了一段“支链”，一来一回边权会被异或两次，直接抵消为 0。

所以无论路径怎么绕，真正留下贡献的只有一条主干简单路径和被完整走完的环。

结合上图，整个算法流程只需三步：

1. 搜集环： DFS 遍历全图，把所有环的异或和全部丢进线性基中。

2. 定基准： 随便找一条从起点到终点的简单路径，记录它的异或和作为初始值。

3. 贪心求解： 拿这个初始值在线性基中查询最大异或和，得出的结果即为答案！

例题2

这道题还是沿用例题一的结论，路径上所有边权的异或和，取决于一条主链与由各个环的异或值

一、 连通分量处理与路径异或和的转化

由于题目不保证图连通，我们需要对每个连通分量独立求解，最后累加答案。

在连通分量内，根据图论结论，两点间任意一条路径的异或和，可以拆分为两部分：

1. 主链异或值：通常选取两点在 DFS 树上的路径异或和。

2. 环的异或组合：图中所有简单环的异或和构成的线性基，其能张成（组合出）的所有异或值。

假设当前连通分量对应的线性基大小为 ，那么该线性基可以组合出 种不同的异或值。因此，对于任意固定的起点和终点，它们之间的路径能产生 种异或结果。

二、 主链异或值的预处理

在进行 DFS 遍历时，我们记录每个节点到根节点的异或前缀和。

对于任意两点，它们的主链异或值，就是这两点异或前缀和的异或结果。这就将复杂的树上路径计算转化为了简单的节点值计算。

三、 按位计算贡献与分类讨论

为了避免枚举所有点对和组合导致的超时，我们采用按二进制位分离计算的方法。针对枚举的第 位，我们观察线性基在这一位上的表现，分两种情况讨论：

• 情况一：线性基中存在某一位为 1 的基底

  这意味着线性基的组合能对第 位产生影响。根据线性基的性质，在其生成的 个组合值中，第 位必定是一半为 0，一半为 1。

  因此，无论两点间的主链异或值在该位是 0 还是 1，最终异或上线性基的结果，该位都有 次为 1。

  该位贡献计算：总点对数

• 情况二：线性基中所有基底的第 位均为 0

  这意味着线性基生成的 种组合值在第 位上全部为 0，无法改变主链的状态。

  此时，要使最终结果的第 位为 1，完全取决于主链（即两点的异或前缀和在该位必须不同）。我们需要统计该连通分量内，异或前缀和在第 位为 0 和为 1 的节点数量。

  该位贡献计算：(该位为 0 的节点数 该位为 1 的节点数)

将所有位、所有连通分量的贡献累加，即为最终答案。