线性基

概述

本节摘自 OI-Wiki。

线性基是向量空间的一组基，通常可以解决有关异或的一些题目。

通俗一点的讲法就是由一个集合构造出来的另一个集合，它有以下几个性质：

• 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
• 线性基是满足性质 1 的最小的集合。
• 线性基没有异或和为 $0$ 的非空子集。
• 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
• 线性基中每个元素的二进制最高位互不相同。

构造方法

插入

将要插入的数 $p$ 转为二进制，从高位到低位扫，对于第 $x$ 位为 $1$ 的，如果 $a_x$ 不存在，则令 $a_x=p$ 并结束扫描；如果 $a_x$ 存在，则令 $p=p \lor a_x$。

求异或和最值

从高位往低位贪心。

求第 $k$ 小异或和（编号从 $0$ 开始）

先构造线性基，使得第 $i$ 个位置上的数字（若不是 $0$）的二进制第 $i$ 位是 $1$。

接下来，再通过用小的数字对大的数字取异或来尽可能减小基中的每个数，于是，比较由基底用异或运算得到的结果的大小，只需要知道 $\sum 2^{\text{用到的基底编号}}$ 的相对大小。

给定 $k$ 时，设基中有 $n$ 个非零的数字，若 $k \ge 2^n$，则无解；否则，用二进制分解来构造解。

例题：线性基

例题：带时间戳的线性基

正交线性基、线性基求交

参考资料：神秘算法 —— 线性基求交 - CharlieVinnie - 博客园。

例题