浅谈线性基

简述

线性基是竞赛中常用来解决子集异或一类题目的算法。

基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。

——百度百科

要了解何为线性基，首先你不需要掌握基是什么。

你只要知道：线性基是由一个数的集合构造出来的另一个数的集合，并且满足一些性质，使其能解决有关异或的一些题目。

性质

1. 原集合里的任何数都可以用线性基中某些数的异或和表示。
2. 线性基中任意数的**异或和不等于 $0$**。
3. 线性基的大小之和原集合的大小有关，并且是满足性质 $1,2$ 的前提下，大小最小的。换句话说，就是线性基的大小固定且最小。

例子

如果有一集合 $A={110,011,101}$，那么 $A$ 的线性基可以为 ${110,011},{110,101},{011,10}$。

如果有一集合 $B={10,11}$，那么 $B$ 的线性基可以为 ${10,11},{10,01},{01,11}$。

很显然，以上均是合法的线性基，满足所有线性基的性质。

由此可见，集合的线性基可能不唯一，线性基中的元素可以不在原集合中。

证明

我们可以采用反证法：（可能不太严谨）

设线性基 $S={a_1,a_2,\dots,a_n}$，若有其子集 $P={a_1,a_2,\dots,a_k}$，并且满足 $a_1\oplus a_2 \oplus \dots \oplus a_k=0$，那么 $a_1=a_2\oplus a_3\oplus \dots \oplus a_k$，则舍弃 $a_1$ 后一定可以通过剩余的元素异或出所有 $a_1$ 所需要参与的异或值。

那么 $a_1$ 就可以舍弃，用别的数来代替 $a_1$，使线性基的个数减少。

而线性基又是大小最小的（性质 $3$），与假设矛盾，证毕。

线性基的构造

讲完了何为线性基，那么问题来了，给定一个集合，我们如何构造它的线性基呢？

设数组 $d$ 表示线性基，下标从 $0$ 开始，不难得出其构造的代码：

I void Add(LL x){
    RI i;for(i=60;~i;i--) if(x>>i&1)//从高到低枚举二进制数的每一位，如果该位为1
        if(d[i]) x^=d[i];
        else{d[i]=x;break ;} //插入成功后直接退出
}

据此，我们可以得到一个关于 $d$ 数组的性质：存入 $d[i]$ 的元素的第 $i$ 位为 $1$，并且 $d[i]{(2)}$ 的最高位就是第 $i$ 位。（假设 $x{(2)}$ 表示 $x$ 的二进制表示）

构造的正确性证明

略（只要分别证明其三个基本性质即可。

经典应用

1. 给定一个集合，询问某个数能否被表示成集合中某些元素的异或和。
2. 给定一个集合，求取一些数异或和的最大值/最小值。
3. 给定一个集合，取任意多个数字异或，求异或和的第 $k$ 小。
4. 线性基的删除操作

我们来一个一个分析。

1. 能否表示成集合中某些元素的异或和

这个问题其实十分简单，首先构造出这个集合的线性基，然后尝试把这个数插入线性基，如果可以，就表明不能；否则肯定可以选取某些线性基内的数异或得到该数字。

I int Add(LL x){
    RI i,flg=0;for(i=60;~i;i--) if(x>>i&1)
        if(d[i]) x^=d[i];
        else{flg=1;break ;} 
    return !flg;
}

2. 求最大值/最小值

很显然，如果能使高位为 $1$，那么宁可舍弃低位的 $1$，所以只要从高到低枚举每一位是否能使答案的该位变为 $1$ 即可。

I LL GetAns(){
    LL Ans=0;RI i;for(i=60;~i;i--) if((Ans^d[i])>Ans) Ans^=d[i];
    return Ans;
}

如果是求最小值，那么只要先判断下是否能构成 $0$，即线性基的大小如果小于集合的大小，那么存在某些数的异或和为 $0$，那么 $0$ 就是最小值。

如果线性基的大小刚好等于集合的大小，那么最小值一定是最小的 $d[i]$。

因为我们在构造线性基的时候保证了每一位的 $d[i]$ 的最高位必定是 $i$，因此用最小的 $d[i]$ 异或别的数，得到的结果必定大于 $d[i]$，证毕。

3. 求异或和第 $k$ 小

首先我们可以把我们现有的线性基变换一下。

具体地，枚举每个 $d[i]$，再枚举 $j$（从 $i-1$ 到 $0$），如果 $d[i]_{(2)}$ 的第 $j$ 位是 $1$，那么令 $d[i]\oplus=d[j]$。根据线性基的三个性质，不难证明，处理过后的集合仍然是集合的线性基，只是对于每个 $d[i]$，把 $i$ 位之后的所有都异或成了 $0$。

新的线性基大致长成这样：（$x$ 表示可能是 $0$ 或 $1$）

1xxxx0xxx0x
000001xxx0x
0000000001x

不难发现，这个线性基使每个 $d[i]$ 只有其第 $i$ 位为 $1$，那么只要使 $k$ 的每一位和 $d[i]$ 相对应，异或上第 $i$ 大的元素，即可求出最终的 $Ans$。

I void Work(){
    RI i,j;for(i=1;i<=60;i++) for(j=i-1;~j;j--) if(d[i]&(1LL<<j)) d[i]^=d[j];
}
I LL K_th(LL k){
    if(tot<n&&!--k) return 0;//tot表示线性基中的元素的个数，n表示序列长度。注意可以异或出0的情况
    LL Ans=0;RI i;for(Work(),i=0;i<=60;i++) if(d[i]) k&1&&(Ans^=d[i],0),k>>=1;
}

4. 线性基的删除操作

在线

如果要求删除的 $x$ 刚好在线性基外，即删除后对线性基没有任何影响，那么直接删除即可。

如果要求删除的 $x$ 在线性基内，此时，我们需要构造出一个集合 $P$，记录线性基中这个数插入进来时异或过那些数，然后找到线性基中最小的并且 $P$ 包含 $x$ 的数，让他异或线性基中其他包含 $x$ 的数即可（包括自己），这样就消去了 $x$ 在线性基中的影响，即用最小的数代替了他。

离线

上面的问题并没有强制在线，所以也可以离线做，离线的话其实更简单。

我们可以找到线性基中对于每一个数，可以代替他们的那些数，那么可以使线性基优先存删除时间晚的，那么就消除了上面的把他删掉之后可能序列中其他的数可以填进来这样的问题，其余操作一样。

具体实现起来就是在插入一个新数的时候，对比一下这个数的删除时间和当前枚举到的线性基的某一位的删除时间，假如比他晚就直接替换掉，否则异或它然后继续枚举。这样就少维护了一个集合。

习题

[checkbox checked=”true”]LuoguP3812 【模板】线性基[/checkbox] [checkbox checked=”true”]【例题1】彩灯[/checkbox] [checkbox checked=”true”]【例题2】元素[/checkbox] [checkbox checked=”true”]K小异或和[/checkbox] [checkbox checked=”true”]路径最大异或和[/checkbox] [checkbox checked=”true”]有趣的三元组[/checkbox] [checkbox checked=”true”]出现位置[/checkbox]