线性基(Linear Basis)

线性基(Linear Basis,异或线性基)是把一组整数视为二进制向量,在异或运算这一特殊加法下构造出的一组线性无关基。它由不超过位数个元素组成,却能通过异或组合表示原集合能异或出的全部数值,从而把对整个集合的异或询问压缩到对这组基的操作上。

概述

在异或意义下,整数集合构成线性代数中的向量空间,每个数是二进制上的向量,异或相当于按位加法。线性基就是这个空间的一组基底,规模仅与二进制位数相关。借助它,原本涉及指数级异或组合的问题,可化为对至多几十个基元素的贪心或线性代数处理,效率极高。

核心特点

• 插入构造:逐个把数从最高位开始尝试插入,若对应最高位尚无基元素则占据该位,否则与该位基元素异或后继续向低位处理。
• 可表示性:一个数能被原集合异或表示,当且仅当它能被线性基异或消成零。
• 异或最大值:从高位到低位贪心,若异或当前基元素能使结果变大就异或,得到全体子集异或的最大值。
• 规模有限:基元素个数不超过数值的二进制位数,与集合大小无关,插入和查询都极快。

应用场景

线性基常用于求集合任意子集异或的最大值、最小值和第 k 小值,判定某数能否由子集异或得到,统计不同异或结果的数量,以及图论中处理环的异或路径问题。它是竞赛中异或类题目的通用利器,也可推广到有理数域上的线性无关判定。

常见问题

问:线性基能求异或第 k 小吗?答:可以。先把线性基化简为每一位相互独立的规约形式,再将 k 按二进制拆分,选取对应的基元素异或起来即得第 k 小的异或值。

问:线性基和高斯消元是什么关系?答:构造线性基本质上就是在二进制向量空间上做高斯消元求主元,只是异或代替了普通加减,结果得到一组张成相同空间的线性无关向量。