若集合\(B\)=集合\(S\)能异或出的数字的集合且\(|B|\)最小，则称集合\(B\)为集合\(S\)的线性基
依次插入集合\(S\)中的每个数字\(x\)，我们将\(x\)从高位向地位遍历
假设当前遍历到第\(i\)位，且\(x\)二进制下第\(i\)位为\(1\)：
若已经存在\(p_i\)，那么\(x\)异或\(p_i\)，否则\(p_i=x\)，结束
为什么这样做？
首先一个数插入线性基后，那么这个数字一定能被线性基表示出来，因为它本身就是线性基某几位数字异或后再插入进去的
如果一个数字没能插入线性基，那么说明这个数字被线性基中的数字异或到了\(0\)，已经可以被表示出来了，可以保证集合最小
求\(n\)个数字中任选几个的异或最大值
我们构造出线性基,显然线性基有一个性质：\(p_i\)在二进制下的最高位是第\(i\)位
那么从高位到地位贪心：如果当前答案异或\(p_i\)更优，那么就让\(ret\)异或\(p_i\)
我们构造出线性基之后对线性基进行消元，使得只有\(p_i\)的第\(i\)位为\(1\)，然后我们把中间空出来的位置去掉，对\(k\)二进制分解，如果\(k\)第\(i\)位是\(1\)就异或上\(p_i\)
坑点：线性基不能异或出\(0\)，但是原集合是有可能异或出\(0\)的
很好判断，如果线性基集合大小 小于 原集合集合大小，说明原集合中有些数字在插入的时候被异或成了\(0\)而没有插入，所以将\(k\)改为\(k-1\)即可
从高位向地位扫，如果这一位是\(1\)就异或\(p_i\)，到最后数字变成\(0\)就可以被异或出
把\(S\)的所有子集的异或和算出，求\(x\)的排名
结论题：线性基中每个异或值出现的次数是\(2^{n-|B|}\)
我们考虑把所有数字都插入线性基，那么新的线性基将是原来的线性基加上\(n-|B|\)个\(0\)，每个数字都可以自由的选择\(0\)来异或
先假设我们有一条无环的简单路径
我们可以从路径上的一个点，出发到一个环，然后绕环一圈，再原路返回
这样我们原本的路径权值就异或了一个环上的权值
观察到每个环我们都可以自由的选择，那么问题就变成了一条路径权值异或几个环的权值最大，裸的线性基问题
至于简单路径随便选一条就行了，如果有多条说明它们本身成环
上一题加强版
按二进制每一位考虑：如果线性基中存在某一位\(w\)是\(1\)，那么将一共有\(2^{|B|-1}\)个数字\(w\)是\(1\)
如果线性基中某一位\(w\)是\(0\)，那么线性基中所有\(2^|B|\)种组合第\(w\)位都将是\(0\)
我们直接枚举二进制位\(w\)，如果存在\(p_w\)，那么说明无论\(d_u\)异或\(d_v\)是\(0\)还是\(1\)，都有\(2^{|B|-1}\)种方案让答案变成\(1\)
对答案的贡献是\(2^w*2^{|B|-1}*C_{n}^{2}\)
否则，\(d_u\)和\(d_v\)中必须恰好一个\(w\)位是\(1\)，设\(w\)位是\(1\)的\(d\)有\(x\)个，则贡献是\(2^w*2^{|B|}*x*(n-x)\)
原文：https://www.cnblogs.com/knife-rose/p/12372175.html