线性基

这几天很困而且肚子吃坏了导致这一章学的奇慢，此事在我的犇犇中亦有记载。

线性基就是向量基底。

oi里头喜欢用异或线性基，就是把原本基底表示的求和改成异或。

所以可以拿来解决异或问题。

称集合 \(B\) 为 \(S\) 的线性基当且仅当 \(B\) 对于它代表的集合 \(S\) 满足 \(S\) 任一子集的异或和均可以通过 \(B\) 的子集异或和表示，且 \(B\) 是所有那样的集合中 \(|B|\) 最小的若干个。

对于线性基的构造：参考高中数学的基底 \(\{u\}\)，每一个基底中的元素 \(u_i\) 都至少应该表示出唯一的一维信息，不唯一的信息则可以用其他于那些维唯一的基底元素抵消掉，进而显然存在一个 \(D\) 维方程组使得对于任意一维 \(D_0\) 满足

就能转成正交基。

异或线性基是一个道理的，相当于在一个 \(logV\) 维的空间中的一组基底，每个二进制位对应的那个 \(u\) 可以唯一地表示出那一维度的 \(1\)，进而让其最高位就是那个 \(1\) 就能保证唯一性质了。

所以有一种贪心构造。

	int p[32];
	inline void insert(int x){
		for(int i=31;i>=0;i--){
			if((x>>i)&1){
				if(!p[i]){
					p[i]=x;
					return ;
				}
				else x^=p[i];
			}
		}
	}

对于当前插入的 \(x\)，必须保证其成为基底的第 \(i\) 项时前 \(i-1\) 位没出现过 1，那就可以在前 \(i-1\) 位的每个 1 处异或一下那一位的基底。

看一下这个线性基能干啥。

根据上面的构造方式，把线性基从高往低扫一下贪心取最大就能获得原数组的最大异或和，传参一个询问值就能解决原数组的子集和询问值的最大异或和。

板题

又根据定义，线性基的元素个数最小，所以无论怎么插生成的线性基元素个数都一样。就可以解决一类贪心问题。

元素

新nim游戏

线性基可以求第 \(k\) 大/小异或值，还能统计个数。

P4869

显然线性基能唯一地表示出 \(2^{|B|}\) 个值，但是原数组共有 \(2^n\) 个异或值，剩下数组中的 \(n-|B|\) 个元素肯定存在和 \(B\) 子集异或和为 0 的情况，那不妨就把它们看作是 0，选不选都不影响异或值，则每个 \(2^{|B|}\) 个去重的异或和应当出现了 $2^{n-|B|} $ 次。

神秘题 和它的 多倍经验

不妨现在已经构造出了一种随机赋边权的方案，使得对于每个会使图不连通的询问边集 \(E_0\) 中包含的图的割 \(E'\) 的异或和为 0。这样只需对询问边集建线性基即可。这tm谁能想到

然后看怎么构造，考虑逐步扩展问题规模，对于只有一个点只要出边异或和为 0 即可。对于两个点的情况发现可以靠和异或一样效果的容斥抵消成刚才的结论。对于 \(n\) 个点是同理的。所以考虑生成一个赋权方案使得每个点的出边异或和为0。对于非树边就随机权值，树边就给成已确定的权值的异或和，不难发现从叶子赋到根是正确的。

shallot

发现可以线段树分治每个元素存在时的贡献，然后没了。

幸运数字

\(n\) 啥的不大时限还贼宽直接倍增维护 \(2^i\) 级父亲线性基乱搞就能秒。

最大xor和路径和梦想封印

这种题就是说路径是非简单路径。仔细想一下环可以拿来优化答案，链可以拿来跑答案，把每个环的贡献存到线性基里就可以了。

梦想封印那道题离线拆边改加边然后拿set维护一下线性基，每次加边就重构，是 \(O(log^2n)\) 的。