线性基学习笔记

不知道为啥之前那篇突然锅了打开就出错,于是重发了遍,加了$latex$(虽然事实上并没有啥意义$QwQ$

定义

线性基其实就是构造出一组序列$p_0,p_1,...,p_n$,使得这组序列等价于原集合且最小.

可以理解为原集合的一个压缩

umm其实我觉得定义没有太大的用再了解下性质就可以进入正题辣

线性基有一些性质：

1.线性基的异或集合中不存在$0$,也就是说,中线性无关的极大子集

2.线性基中每个元素的异或方案唯一,也就是说,线性基中不同的异或组合异或出的数都是不一样的(这个与性质1其实是等价的.因为线性无关鸭$QwQ$

3.线性基的二进制最高位互不相同

4.如果线性基是满的,它的异或集合取值范围为$[1,2^n-1]$

5.线性基中元素互相异或,异或集合不变(因为它是个压缩,能$get$趴?

然后就港下操作和应用好了$quqqqqq$

应用的话目前学到了的有三种:

　　首先最直接的可以用来高斯消元处理线性相关

　　然后还可以求,第$k$大

　　然后求异或和最大的时候用它可以按位贪心了

$umm$然后港下它滴实现?

构造:

直接对读入的数二进制地从前往后扫

如果扫到一个位置是$1$就判断一下,如果已经有这一位是$1$的数了就异或一下这个最高位是$1$的数

如果没有最高位这里是1的数就放进去并停止扫描

然后就成功构造完成辣!

可以发现这样的话我们放入一个数就只会有俩结果

第一个,能扫到,于是在过程中就会被放进去并停止扫描

第二个,一直到了最后它变成$0$就退出了,这就说明它是能被表示出来的了(就可以把所有把它的有$1$的位数作为最高位的线性基异或起来就能表示出来,$get$?

还是,放下代码趴

合并:

线性基的合并就直接合并就好了鸭,放下代码$QwQ$

这儿是代码QwQ

查询是否能表示出:

在插入那一段中我们港,如果它变成$0$说明它可以表示出来了,所以我们就能$get$辣,直接$insert$操作修改一下就欧克

查询$max$:

两种,分别港下$QwQ$

第一个是可以直接每次判断异或这个基底之后会不会变大,会就异或就欧克

另一种因为和后面那个第$K$大一块儿说所以看后面趴$QAQ$

查询第$k$大:

就构造完线性基之后对它$rebuild$一下,使得每一位最多有一个数为$1$

具体的实现就跟高斯消元似的搞下就好

然后假如当前位为$1$,且后面有$cnt$位,显然比它小的就是有$2^cnt$个($0$这种细节什么的特殊考虑下就好,,,

然后就欧克了,也放下代码趴$QwQ$

View Code

最后放下题单,,,都是些比较基础的,只有线性基的知识点的题目$QwQ$

(有几个[x]的链接是题解,,,其他的是题目$QwQ$

[X] 线性基模板

[X] 元素

[X] 新Nim游戏

[X] 最大XOR和路径

[X] 幸运数字

[ ] 玛里苟斯

[ ] albus就是要第一个出场

[X] XOR