首页 > 笔记 > 线性基学习笔记

线性基学习笔记

定义

不想再扯些线性代数啥的东西了。OI中线性基就是相当于有一个数集S,找出它所有子集异或和构成的数集T。线性基就是另一个数集S',它的所有子集异或和也能构成T。相当于压缩了S。

可以证明S'的元素数量是log级的。

求法

考虑插入一个数$x$,那就扫描它的二进制,扫描到第$i$时,如果$p_i$不存在,就令$p_i=x$,否则$x=x xor p_i$。

$x$的结局是,要么加入线性基,要么经过一系列操作过后,变成了0。

后面的是要先用下面的行消自己,再用自己消上面的行。为了维护一个上三角矩阵。

应用

存在性

把数按插入的过程加入线性基。看看是不是最后变成0了。

最大值

从高位到低位扫描线性基。

如果异或后可以使得答案变大,就异或到答案中去。

最小值

找到最小的线性基就好了

第k小

所以查询的时候将k二进制拆分,对于1的位,就异或上对应的线性基。

最终得出的答案就是k小值。

例题

最大异或和

SGU275
bzoj4269

第k大异或和/异或和是第几大

bzoj2844
hdu3949

求所有异或值的和

bzoj2844
bzoj3811

图上的例子

bzoj2115
bzoj2322


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×