線性基學習筆記

概念

定義：給定數集 \(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\) 小值

不想說明。