實際上就是通過一個可重集 \(A\) 來生成另一個不可重集 \(B\)，使得 \(B\) 滿足一些性質(zhì)。

有點類似于有一些向量，找出能表示所有這些向量的基底向量。

本文主要涉及的是異或線性基。

1. 線性基的性質(zhì)

性質(zhì)一

\(A\) 中任意數(shù)都可以通過 \(B\) 中若干個數(shù)異或得到。

性質(zhì)二

\(B\) 集合中不存在兩個子集異或和一樣。

性質(zhì)三

\(|B|\) 是確定的，且在保證性質(zhì)一的情況下是最小的。

性質(zhì)四

對于 \(B\) 中任意子集， 存在 \(A\) 的子集與它異或和相等。

性質(zhì)的證明

我們在將 \(A\) 中一個元素 \(w\) 加入時，若 \(B\) 中存在一個子集的異或和 與 \(w\) 相等時，則不加入 \(w\)。

那么這樣我們就可以保證性質(zhì)二。

考慮反證：

若 \(B\) 中存在子集 \(\{x_1,x_2,...,x_k\}\) 與 \(\{y_1,y_2,...,y_m\}\) 滿足 \(\text{xor}_{i=1}^k\ x_i=\text{xor}_{i=1}^m\ y_i\)。我們就可以將最晚加入的數(shù) （設(shè)為 \(x_1\)）放在等號一側(cè)，將剩下的全部放在等式右側(cè)，則有 \(x_1=\text{xor}_{i=2}^k\ x_i\ \text{xor}\ \text{xor}_{i=1}^m\ y_i\)。

而此時不符合我們將 \(x_1\) 加入的條件，也就是我們不會加入 \(x_1\)，所以不會存在這種情況。

那么性質(zhì)一也很好說明，每一次沒被加入的數(shù)都可以表示出來，加入的數(shù)在加入后也可以表示出來。

然后就是性質(zhì)三。其實發(fā)現(xiàn)線性基的大小跟插入順序無關(guān)。如果一個元素在一種順序下不能插入，但是在另一種順序下插入了，那么一定存在另一個元素原本能插入，但是在后者的順序下插入不了。

因為在保證性質(zhì)一后得到的線性基，從里面任意刪除一個元素都無法表示 \(A\) 的所有元素，所以得到的線性基的大小一定是最小的。

然后是性質(zhì)四。因為我們 \(B\) 里的數(shù)都可以通過 \(A\) 表示出來，所以 \(B\) 的任意子集也可以表示。

2. 線性基的構(gòu)建

有兩種方式構(gòu)建線性基。

一種是貪心構(gòu)造，一種是高斯消元構(gòu)造，但是前者支持在線。后者的優(yōu)勢在于高斯消元后的矩陣是一個行簡化階梯形矩陣。

這里只給出貪心法的構(gòu)造，因為貪心法更常用且更好寫，最主要是筆者不會行列式，所以后面的性質(zhì)對我來說沒什么用。

貪心法

這里貪心法構(gòu)造出的方案滿足 \(B\) 中元素的二進制最高位不同。

設(shè) \(p_i\) 為線性基 \(B\) 中二進制最高位為 \(i\) 的線性基大小。當(dāng) \(p_i=0\) 時，說明這樣的數(shù)不存在于線性基內(nèi)。

現(xiàn)在考慮加入一個數(shù) \(w\)。

從大到小枚舉每一位，若 \(w\) 當(dāng)前位為 \(1\)，則判斷 \(p_i\) 是否為 \(0\)，如果為 \(0\) 則讓 \(p_i=w\)，然后退出。如果 \(p_i\neq 0\)，則讓 \(w\gets w\ \text{xor}\ p_i\)，這樣能把 \(w\) 的這一位變?yōu)?\(0\) 從而降低它的最高位。

顯然當(dāng) \(w=0\) 時它能被線性基內(nèi)的數(shù)所表示。

單次插入為 \(O(\log V)\)，\(V\) 為值域大小。

注意：當(dāng) \(p_i\neq 0\) 時，\(p_i\) 的第 \([0,i-1]\) 位也可能為 \(1\)。也就是可能 \(p_i\neq 2^i\)。

void insert(int w)
{
	for(int i=r;i>=0;i--) //r為所有數(shù)的二進制最高位的最大值 
	{
		if(w&(1<<i))
		{
			if(!p[i]) return p[i]=w,void();
			w^=p[i];
		}
		if(!w) return;
	}
}

3. 線性基的操作及技巧

求異或最大值

求 \(x\) 與 \(A\) 的子集的最大異或和。

因為構(gòu)建的線性基的滿足二進制最高位不同，所以我們從大到小枚舉最高位，然后依次判斷取了過后是否更優(yōu)。

時間復(fù)雜度 \(O(\log V)\)。

int ans=x;//x為初始值。也就是找x與A的子集的異或和最大值
for(int i=r;i>=0;i--) //r為值域的二進制的最高位 
{
	if((ans^p[i])>ans) ans^=p[i];
}

求異或最小值

如果是求 \(x\) 與 \(A\) 的子集的異或和最小值，可以類似于上述求最大值的過程，從高位向低位枚舉，如果取了更小就取。

如果是求 \(A\) 的非空子集的異或和最小值，那么檢查 \(A\) 中是否有元素未被插入線性基，如果有則答案為 \(0\)，否則答案為最小的非零 \(p_i\)。

小Trick：當(dāng) \(|A|>r\) 時，其中 \(r\) 為值域的二進制最高位，則一定有元素沒被插入線性基。因為線性基最多只能插入 \(r\) 個元素。

時間復(fù)雜度 \(O(\log V)\)。

求異或k小值

因為求出的線性基 \(p_i\) 可能會存在除了第 \(i\) 位為 \(1\) 以外其他位也有 \(1\)，就可能導(dǎo)致用一個大數(shù)異或一個小數(shù)可能比不異或小數(shù)更小。所以我們需要對線性基先處理一下。

對于 \(p_i\) ，枚舉 \(j\ \text{from}\ (i-1)\ \text{to} \ 1\)，然后如果 \(p_i\) 的第 \(j\) 位為 \(1\) 的話則讓 \(p_i\gets p_i\ \text{xor}\ p_j\)。注意這里的 \(i\) 需要從小到大枚舉。

那么此時用一個大數(shù)異或上小數(shù)就一定大于一個大數(shù)了。

將 \(k\) 轉(zhuǎn)化為二進制數(shù)，如果 \(k\) 的第 \(d\) 位為 \(1\)，則答案異或上 線性基中第 \((d+1)\) 小的元素。

別忘了先把 \(0\) 給判掉。如果最小值為 \(0\)，則需要讓 \(k\gets k-1\)。

預(yù)處理時間復(fù)雜度 \(O(\log^2 V)\)，單次查詢 \(O(\log V)\)。

void operate()
{
	for(int i=0;i<=r;i++)
	{
		for(int j=i-1;j>=0;j--)  if(p[i]&(1<<j)) p[i]^=p[j];
	}
}
int get_kth(int k)
{
	if(k==1&&num<n) return 0;//提前判掉最小值為0的情況
	//num為線性基內(nèi)元素個數(shù)
	if(num<n) k--;
	
	int res=0;
	for(int i=0;i<=r;i++)
	{
		if(p[i])
		{
			if(k&1) res^=p[i];
			k>>=1;
		}
	}
	return res;
}
int main()
{
	operate();//先預(yù)處理 
	return 0;
}

詢問存在性

判斷一下能否插入線性基即可。時間復(fù)雜度 \(O(\log V)\)

線性基求并

對線性基 \(B_1\) 和 \(B_2\) 求并，直接將 \(B_2\) 中的每一個元素加入 \(B_1\) 即可。

時間復(fù)雜度 \(O(\log^2 V)\)。

帶刪除線性基

這里只給出離線做法。

那么求出每個元素被刪除的時間戳 \(d_i\)，如果沒被刪就是正無窮。

對于線性基，同時維護一個 \(d'_i\) 表示 \(p_i\) 的時間戳。

然后在加入 \(w\) 時， \(w\) 的第 \(i\) 位為 \(1\)，進行分類討論：

• 當(dāng) \(p_i=0\) 時，則讓 \(p_i=w,d'_i=d_w\)。
• 當(dāng) \(p_i\neq 0\) 時，如果 \(d'_i<d_w\) 時，則 \(\text{swap}(p_i,w)，\text{swap}(d'_i,d_w)\)。

這樣再進行操作時，只需判斷 \(d'_i\) 是否 \(\ge\) 當(dāng)前時間戳即可。如果 \(\ge\) 當(dāng)前時間戳，說明 \(p_i\) 還存在，否則就當(dāng) \(p_i=0\)。

void insert(int w,int dd)
{
	for(int i=r;i>=0;i--)
	{
		if(w&f[i])
		{
			if(!p[i]) return p[i]=w,d[i]=dd,void();
			if(dd>d[i]) swap(p[i],w),swap(d[i],dd);
			w^=p[i];
		}
		if(!w) return;
	}
}

4. 基礎(chǔ)題

P3812【模板】線性基

給定 \(n\) 個整數(shù)（數(shù)字可能重復(fù)），求在這些數(shù)中選取任意個，使得他們的異或和最大。

$ 1 \leq n \leq 50, 0 \leq S_i < 2 ^ {50} $

直接全部插入線性基，再求最大值即可。時間復(fù)雜度 \(O(n\log V)\)。

不明白數(shù)據(jù)范圍為啥開這么小。

P4570 [BJWC2011] 元素

求出一個長為 \(n\) 的序列 \(a\) 的異或線性基，對于每一個數(shù)，把他插入線性基的代價為 \(d_i\)。求線性基的最大代價總和。

\(n\le 10^3,d_i\le 10^4,a_i\le 10^{18}\)。

可能有些同學(xué)會有疑問啊？如何求才能使代價最大呢？dp？

其實很簡單，因為線性基的大小是定的，所以直接按 \(d_i\) 從大到小的順序加入 \(a_i\) 即可。如果成功插入，則答案加上 \(d_i\)。可以證明這樣貪心一定是對的。

時間復(fù)雜度 \(O(n\log V)\)。

P4301 [CQOI2013] 新Nim游戲

一個長為 \(n\) 的正整數(shù)序列，你可以刪去一個子集。刪完后對手也會刪去一個沒被刪過的數(shù)的子集。

然后你們在剩余的數(shù)中玩nim游戲，你先手。

求出最終你有必勝策略的情況下，你刪去子集內(nèi)元素之和的最小值。

\(n\le 100,a_i\le 10^9\)。

實際上就是想要你刪去一個子集后剩下的子集不包含異或和為 \(0\) 的非空子集。

相當(dāng)于求出將所有數(shù)加入線性基后，沒被成功插入的數(shù)的和的最小值。

直接從大到小排序，然后類似上一道題處理就行了。

5. 進階題

P4151 [WC2011] 最大XOR和路徑

一個無向連通圖，一條路徑的長度為邊權(quán)異或和。求出 \(1\) 到 \(n\) 的最長路徑。

\(n\le 5\times 10^4,m\le 10^5,w\le 10^{18}\)。

你會發(fā)現(xiàn)最終的路徑可以表達(dá)為 \(1\) 到 \(n\) 的一條鏈 \(+\) 若干個簡單環(huán)。而且這條鏈?zhǔn)侨我獾模驗槲铱梢酝ㄟ^加入若干與鏈有公共邊的簡單環(huán) 使得 這條鏈“變成”了另一條鏈。

因為一個數(shù)異或上自己等于 \(0\)。所以一條路走兩遍貢獻為 \(0\)。所以一個點出發(fā)到達(dá)一個簡單環(huán)，繞一圈后再回來的貢獻其實就是簡單環(huán)上邊權(quán)的異或和。

而簡單環(huán)是可以拼接的，因為兩個簡單環(huán)的公共部分的異或和貢獻為 \(0\)。

于是我們可以建一棵以 \(1\) 為根的dfs生成樹。設(shè) \(dis_u\) 為 \(1\) 到 \(u\) 的樹上路徑異或和。于是對于所有非樹邊，與樹邊構(gòu)成的簡單環(huán)為 \(dis_u\ \text{xor}\ dis_v\ \text{xor}\ w\)。

于是將所有只有一條非樹邊的簡單環(huán)加入線性基。因為簡單環(huán)可以合并，所以相當(dāng)于我們把所有簡單環(huán)都加入了。

于是最終答案就是 \(dis_n\) 與這個線性基的最大值。

時間復(fù)雜度 \(O(n\log V)\)。

P3292 [SCOI2016] 幸運數(shù)字

一棵 \(n\) 個節(jié)點的樹，邊帶權(quán)。 \(q\) 次詢問，查詢 \(x\) 到 \(y\) 的路徑中選出若干條邊，求出所有情況下，能選出的這些邊的最大異或和是多少

\(n\le 2\times 10^4,q\le 2\times 10^5,w\le 2^{60}\)。

不難想到，我們需要維護出 \(x\) 到 \(y\) 路徑的線性基。于是可以考慮用倍增+線性基合并去做。

這樣時間復(fù)雜度是 \(O(n\log n\log V+q\log n\log ^2V)\)。

然后在 6.0s 的實現(xiàn)下居然過了。

但是很慢，考慮更快的做法。

我們可以對于 \(u\) ，維護出 \(1\) 到 \(u\) 的路徑的線性基 \(b_u\)。但是這里是類似“帶刪除線性基”的，對于 \(p_i\neq 0\) 且 \(w\) 這一位為 \(1\) 的情況下，我們優(yōu)先選深度較大的。當(dāng) \(dep_w>dep'_i\) 時就選 \(w\)，否則選 \(p_i\)。

于是對于查詢 \((x,y)\)，我們先合并 \(b_u\) 和 \(b_v\)，同樣優(yōu)先取深度最優(yōu)的。然后對這個線性基求最大值時，當(dāng) \(dep'i<dep_{\operatorname{lca(u,v)}}\) 時，我們把 \(p_i\) 當(dāng)作 \(0\)。其余不變。

于是這樣就能在 \(O(n\log n+q\log^2V)\) 解決問題。

6. 結(jié)語

推薦的是 這個題單，還有 P3733 [HAOI2017] 八縱八橫。

參考文獻：

洛谷日記-【學(xué)習(xí)筆記】淺談異或線性基

oi wiki - 線性基