写在前面

刚刚体验到正版office2016快乐的我
因为懒得写数学公式
还是来到这里写一篇讲义$QAQ$
刚刚学习 发现什么不对的随时叫停喷我就好

有关线性基

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

一些定义

1.异或和

设$S$是一个无符号的整数集(下文我们约定若没有特殊的说明所有的集合均为无符号的整数集)
这样的话我们定义这个集合的异或和$xor-Sum$
$xor-Sum(S)=S_1xorS_2xor...xorS _ {|S|}$

2.张成

设$T \subseteq S$,那么所有这样的子集$T$的异或和组成的集合称为集合$S$的张成,记作$span(S)$。
这个东西说的就是在$S$里面选出任意个数,它们的异或和的所有可能的结果组成的一个集合

3.线性相关

对于一个集合$S$,如果存在一个元素$S_j$使得$S$在去除了这个元素之后得到的集合$S'$的张成$span(S')$包含$S_j$那么我们说这个集合线性相关
更形象地,可以表示为,对于一个集合$S$,存在一个元素$S_j$,可以用其他的元素异或得到
相对地,不存在这样的元素我们就说这个集合$S$线性无关
一个显然的结论是
对于一个线性相关的集合$S$,去除$S_j$之后这个集合的张成不变

线性基

我们称集合$B$是集合$A$的线性基,当且仅当
1.$S \subseteq span(B)$,即$S$是$B$的张成的子集;
2.$B$是线性无关的
其中集合$B$的元素的个数,叫做线性基的长度

性质

线性基有如下基本的性质:
1.$B$是极小的满足线性基性质的集合,它的任何真子集都不可能是线性基
2.$S$中的任意元素都可以唯一表示为$B$中若干个元素异或起来的结果
3.线性基没有异或和为0的子集

线性基的构造与性质

这里讲解一种线性基的构造方法以及特殊的性质
下文中我们讨论这种构造方法的正确性
PS.下文中所有的线性基我们默认是用这种方法构造的线性基
设集合$S$中最大的数在二进制意义下有$L$位,我们使用一个数组$a[0...L]$来储存线性基
这种构造的方法保证了一个特殊的性质:
对于每一个$i$,$a_i$有如下两种可能:
1.$a_i=0$并且只有满足$j>i$的$a_j$的第$i$个二进制位可能是1
2.$a_i \neq 0$并且
(1)整个$a$数组中只有$a_i$的第$i$个二进制位是$1$
(2)$a_i$更高的二进制位一定为$0$
(3)$a_i$更低的二进制位可能是$1$
我们称第$i$位存在于线性基中,当且仅当$a_i \neq 0$
我们可以在这里举个栗子:
我们在这里提出一些可能通过这种办法构造出的$a$数组(右侧是最低的二进制位),当然了我们也提出一些不能通过这种构造实现的,加深大家的理解
首先是可能得到的数组:
0 0 0 0 1
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
1 1 0 1 0
然后是反例
1 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
还有这个
0 1 0 1
0 0 1 0
0 0 0 0
1 0 0 0
这里面第一个$a$数组的第一行有问题
我们发现第一个1不满足性质$2$的$(2)$
第二个$a$数组的第一行有问题
这个东西不满足性质$2$的$(2)$
以上是两个简单的反例说明
接下来我们解释一下上面那个可能得到的数组
这个数组中有两行是$0$
也就是说$a_1=a_3=0$
我们先看性质$1$
发现这个数组满足这个性质
然后对于$a_0,a_2,a_4 \neq 0$
我们来看性质$2$
发现全部满足
所以说这就是我们构造出来的一个合理的线性基

接下来说线性基的动态构造
我们只需要从空的$a$数组开始,每次考虑在当前的$a$数组中加入一个数$t$就行了
加入一个数$t$的方法:
我们从$t$最高位上面的$1$开始考虑我们假设这一位是第$j$位。
首先我们要看一看这一位是不是已经存在于线性基中(我指的是这一位上面的$1$)。
如果存在的话我们需要先将其消去(性质$1$)
消去的方法是异或上$a_j$
然后我们才能继续插入这个数
反之如果这一位不存在于线性基中 我们则可以直接插入这个数
但是在插入这个书的时候我们需要保证如下性质:
$1.$$t$中比$j$这一位高的已经存在于线性基中的二进制位必须是$0$,而这个时候$t$的最高位上面的1必定是第$j$位,所以不用考虑了
$2.$$t$中比$j$位更低的已经存在于线性基中的二进制位上必须是0(性质$2$)。
对于这个保证,我们可以通过枚举$t$中是$1$的这些二进制位来完成
枚举的是$k,k \in [0,j)$对应的元素$a_k$,用类似的方法,$txora_k$,这样我们就消除了这些位上面的1
$3.$$a$中的第$j$位上面只有$a_j$才能是$1$
这里需要考虑两个事情:
$(1)$$a$中比$j$更高的二进制位显然已经是$0$了 所以这里我们无需考虑
$(2)$$a$中在$a_j$之后的元素的第$j$位一定是$0$,对于这一点我们还是可以采取跟之前类似的方法来处理,我们可以枚举$a_j$后面的元素$a_k,k \in (j,L]$,将每个第$j$位上面的$1$异或上$t$

构造流程:
逆序枚举$t$所有$1$的二进制位$j$,对于每个$j$
$1.$如果$a_j \neq 0$那么我们令$t=t^a_j$
$2.$如果$a_j=0$那么我们进行两次枚举
$(1)$枚举$k \in [0,j)$ 如果的$t$二进制$k$位是1那么$t=t^a_k$
$(2)$枚举$k \in (j,L]$ 如果$a_k$的二进制第$j$位是$1$ ,那么$a_k=a_k^t$
然后我们令$a_j=t$,结束数$t$的插入

证明:
首先有关性质,我们发现归纳法就可以证明了
就是正常的那种归纳法 假设$t$成立,我们插入$t+1$看成不成立,然后发现全部成立
我们枚举$S$中的所有元素作为$t$,分别插入,并将数组$a$转化为一个集合$B$(只需要去除重复的为$0$元素即可,显然不为$0$的元素不会重复),此时$B$就是$S$的线性基:

首先,在插入的过程中,我们每次找到$t$最高位上的$1$,然后把它消去,如果最终全部被消去,则表示要插入的$t$已经可以由$a$中一些元素的异或和表示出,此时不需要插入。这样保证了$B$是线性无关的。 对于被实际插入到$a$中的元素,它们在实际插入之前做了一些变换,这些变换都是使它异或上$a$中已存在的元素,或者使$a$ 中已存在的元素异或上它 —— 这些变换都是可逆的,所以用$a$中一些元素的异或和可以表示出这些(实际被插入的)元素。

同时,显然该算法的时间复杂度为$O(logt)$单次插入,空间复杂度同样为$O(logt)$。

各种操作的模板

1.插入

我们经过刚才的叙述
我们发现经过一系列异或之后这个数只有两种结果:
$1.$这个数被插入进了线性基
$2.$这个数变成了$0$
所以模板在下面

2.询问最大值

我们对于每个线性基从大到小询问
异或起来更大我们就记录下来
然后把结果作为答案
所以模板在下面

3.询问最小值

当给出一个$x$之后我们按照上面的方法来就好了
注意的就是这回我们的枚举顺序变成从小到大
然后如果没有的话就更简单了
没有给定值的话我们直接找到最小的一个线性基就行了
所以模板在下面

4.查询k小异或和

这个东西很简单
我们先把每个线性基拆开 拆成只有一位上面是$1$其余都是$0$的
然后我们找到$k$的二进制表示就行了
详细看代码
$tot=-1$

5.两个线性基的合并

不要以为这样有什么技巧
没错就是暴力合并
所以模板在下面

以上就是线性基的大部分模板

一些例题

$1.$bzoj 2460 传送门
$2.$bzoj 4644 传送门
$3.$bzoj 2155 传送门