线性基学习笔记

概念

定义:给定数集 \(S\),以异或运算张成的数集与 \(S\) 相同的极大线性无关集,称为原数集的一个线性基。

简单地说,线性基是一个数的集合。每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原序列中的任何一个数。

性质

  • 性质一
  • 取线性基中若干个数异或起来可以得到原序列中的任何一个数。
  • 性质二
  • 线性基中任意选择若干个数异或
  • 性质三
  • 线性基内部的数个数唯一,且在保持性质一的前提下,数的个数是最少的。

证明

性质二

\(d_i\oplus d_j\oplus d_k = 0\),那么 \(d_i\oplus d_j = d_k\)。由于 \(d_k\) 可以被得到,那么 \(d_k\) 不可能加入线性基。

性质一

分类讨论插入的数 \(x\)
若不能插入线性基,显然就是在线性基中有几个数和它异或之后变成了零,那么也就是说线性基中若干个数异或后可以为 \(x\)

若可以插入,设插入到了第 \(i\) 位。那么 \(x\oplus d[a]\oplus d[b]\oplus d[c]\oplus\dots\oplus d[k]=d[i]\)
\(d[i]\oplus d[a]\oplus d[b]\oplus d[c]\oplus\dots\oplus d[k]=x\)

所以 \(x\) 也可以由线性基中若干个数异或得到。

性质三

如果原集合中每个数都被插入进了线性基,则显然成立,如果插入顺序是 \(a,b,c,x,\dots\)\(x\) 没有被成功插入,就是 \(a\oplus b\oplus c=x\)
那么无论怎么改变顺序也一定有一个数插不进去。所以个数是一定的。

若去掉线性基里面的任何一个数,都会使得原序列里的数无法用线性基里的数异或得到,所以没有多余的元素。

所以线性基的元素个数在保持性质一的前提下,一定是最少的。

基操

插入

\(x\) 转为二进制,从它的高位开始,如果当前位为 \(1\),并且线性基 \(p\) 的第 \(i\) 位上没有数,那就赋成当前值 \(x\)。否则,将 \(x\) 异或 \(p_i\)

则样子能保证 \(x\) 能通过异或的那几个数得到。

void insert(int k) {
	for(int i=60;i>=0;i--) {
		if(!(k&(1LL<<i))) continue;
		if(!p[i]){
			p[i]=k;
			break;
		}
		k^=p[i];
	}
}

最大值

接着采取贪心的思想,从线性基的最高位开始,若当前的答案异或线性基的这个元素可以变得更大,那么就异或它。因为线性基的 \(p_i\) 的最高位一定为 \(i\)

int maxXor(){
	int res=0;
	for(int i=60;i>=0;i--) res=max(res,(res^p[i]));
	return res;
}

最小值

同样是贪心,最大值要看情况。

for(int i=60;i>=0;i--) ans=min(ans^p[i],ans);

\(k\) 小值

不想说明。

热门相关:我的治愈系游戏   富贵不能吟   裙上之臣   裙上之臣   锦庭娇