线性基是一种经常用于解决集合异或问题的数据结构。其实与其说它是数据结构,说它是一种巧妙的构造算法更恰当。
定义
非负整数集合 的线性基 满足一些美妙的性质:
- 是一个集合;
- 能异或出来的所有非负整数, 都能异或出来,但 的所有真子集都不能完全异或出来,也就是说 是极小的;
- 记 能异或出来的所有非负整数集合为 ,那么 中的每一个元素都仅可以被 中的某个特定子集 异或出来;
简单来说,线性基就是一个关于非负整数集合 的特殊的集合,它很小但又可以异或出 能异或出来的所有值。
构造
考虑线性基的构造,可以构造一种特殊的线性基使得:
-
是一个有序序列;
-
对于每个 :
-
要么 中有且仅有 的二进制第 位为 ,且 的二进制最高的为 的位是第 位;
-
要么 且只有所有满足 的 二进制的第 位为可能为 ;
-
-
最大为 ,其中 是值域;
具体方法是,先让 ,然后不断的把 中的元素插入 。一次插入的流程如下:(设插入的非负整数为 )
从高位到低位枚举,假设枚举到第 位,显然若 的二进制中第 位为 则 不可能插入此处,直接跳过即可。否则:
-
若 ,那么此时 肯定无法插入此处。由于要保证性质 2.1 中关于最高位的性质,所以需要删掉 的第 位。又由于要满足线性基的性质 2,所以我们不能直接让 减去 ,而是应该让 ,因为这样可以保证最终插入 的 异或上 还可以表示原来插入的 ,这样也不会让 中的元素能异或出其它的值或让 不再是极小的;
-
若 ,那么:
- 让 异或上所有满足 且 的二进制中第 位为 的 ,这样做是为了保证性质 2.1 中有且仅有 的二进制第 位可能为 的性质,所以要通过异或操作把 (未来的 ) 的这些位删掉,不直接减去 的原因同上。
- 让 ;
- 让所有满足 的 都异或上 ,这样做同样是为了保证性质 2.1 中有且仅有 的二进制第 位可能为 的性质;
- 结束插入;
执行完插入流程后,若 那么插入就成功了,否则就表明当前的线性基中的元素已经能异或出 ,无需插入。但是若 就表明插入失败,即线性基已经能异或出 了。
插入代码如下:
long long a[65];
bool has0;
inline void ins(long long x)
{
for(int i=60;i>=0&&x>0;i--) // 注意一定要倒序枚举!因为要消掉 x 的二进制高位的 1,并且需要对 x 的二进制的低位造成影响
{
if((x>>i)&1) // x 的二进制这一位为 1
{
if(a[i]==0) // 可以插入
{
for(int j=i-1;j>=0;j--) if((x>>j)&1) x^=a[j]; // 这个循环的顺序不重要
// 因为所有满足 j<i 的不为 0 的 A[j] 都不会影响到其它不为 0 的 A[j]
a[i]=x; // 插入
for(int j=i+1;j<=60;j++) if((a[j]>>i)&1) a[j]^=a[i]; // 把所有满足 j>i 且 A[j] 的二进制第 i 位为一的 A[j] 的二进制第 i 位消去
break; // 记得结束插入过程
}
else x^=a[i]; // 不能插入,消去这一位
}
}
if(x==0) has0=true;
}
查询
把非负整数集合 的元素都插入线性基后,线性基能支持几种关于异或的查询。
求 有多少个不同的子集异或和为
首先检查是否能异或出 ,若可以,那么 异或上线性基外的任意几个数得到的 都可以被线性基异或出来,所以答案为 ,其中 。
求 的子集的最大异或和
由于构造出来的线性基满足有且仅有 的二进制中第 位为 ,所以 中参与异或运算的元素越多结果就越大,让所有 异或起来的结果 肯定是 的所有子序列的异或和中最大的。又由于线性基可以异或出 能异或出的所有值,所以 就是 的子集的最大异或和。
代码如下:
inline long long quemx()
{
long long res=0;
for(int i=0;i<=60;i++) res^=a[i];
return res;
}
求 的子集的最小异或和
由于 中参与异或运算的元素越多结果就越大,所以最优的情况显然是只让 中的一个元素参与异或运算,所以返回 中的最小值即可。不过要特判 的情况。
代码如下:
inline long long quemn()
{
if(has0) return 0;
long long mn=2e18;
for(int i=0;i<=60;i++) mn=min(mn,a[i]);
return mn;
}
求 的子集的第 小异或和
首先线性基中的元素是异或不出 的,所以若 可以异或出 ,即 ,那么就需要让 。
由于 中只有不为 的元素才对异或和有贡献,所以不妨用一个数组 依次记录下 中不为 的值。
显然,由于线性基可以异或出 能异或出的所有值,所以 种 的非空子序列都可以异或出互不相同的值,所以若 就无解。
由于构造出来的线性基满足有且仅有 的二进制中第 位为 ,所以对于任意一个 的非负整数 ,任意一个非负整数异或上 得到的结果都它比依次异或上 小,这和二进制很像。
那么解法就很明显了,把所有满足 的二进制中第 位为 的 异或起来,我们就能得到 的子集的第 小异或和。
代码如下:
long long b[65];
inline long long kth(long long k)
{
if(has0) k--;
int len=-1;
for(int i=0;i<=60;i++) if(a[i]!=0) b[++len]=a[i];
long long ans=0;
for(int i=0;i<=len;i++) if((k>>i)&1) ans^=b[i],k^=1ll<<i;
return k>0?-1:ans;
}
额外的操作
线性基还支持一些其它的操作。
合并
两个线性基合并,只需要暴力把一个线性基中的所有元素插入到另一个线性基中即可。容易证明插入完成的线性基还是满足所有性质的。
可持久化
由于线性基数组 很短,所以可以用二维数组来实现可持久化,时间和空间复杂度都是 的。其中 为操作次数, 则表示值域大小。
upd:2025.06.21
带删除
离线可以直接抠背包(线段树分治),做到 ,或者说 ,其中 是维数。
或者可以给每个基打时间戳,插入的时候维护一下每个基的最晚出现时间(适用于双指针)。
而用一堆分讨可以做到在线,单次 或者 (和插入同阶)。
具体的,每个元素插入的时候额外维护一个 表示它最后由那些元素组成(即最后变成某个基或者变成 时具体异或上了原来插入的哪些元素)。
那么分讨一下,假设删除的是 :
- 如果删除的元素不在线性基中,直接删除即可;
- 否则要消去 带来的影响:
- 若存在一个不在线性基中的元素(插入时被消成了 ),满足其 包含 ,那么 将会在这个地方复活,处理一下;
- 否则秩将会减一,此时:
- 找到线性基中最小的, 包含 的基 ;
- 将所有 包含 的基全部异或上 ( 也要异或自己,相当于变成了 );
这样做显然是对的。