線性基學習筆記
概念
線性基是向量空間的一組基，通常可以解決有關異或的一些題目。
性質
線性基有三大性質
\(1\)、原序列裡面的任意一個數都可以由線性基裡面的一些數異或得到
\(2\)、線性基裡面的任意一些數異或起來都不能得到 \(0\)
\(3\)、線性基裡面的數的個數唯一，並且在保持性質一的前提下，數的個數是最少的
線性基的題目一般都是對這三大性質的考察
要想了解性質，我們首先要知道線性基是如何構造的
構造
對原集合的每個數 \(p\) 轉為二進位，從高位向低位掃，對於第 \(x\) 位是 1 的，如果 \(a_x\) 不存在，那麼令 \(a_x=p\) 並結束掃描，如果存在，令 \(p=p\ xor\ a_x\)。
程式碼
void ad(long long now){
for(rg int i=60;i>=0;i--){
if(now==0) return;
if(now&1LL<<(i-1)){
if(d[i]){
now^=d[i];
} else {
d[i]=now;
return;
}
}
}
}
證明
對於性質一，分兩種情況討論
如果 \(x\) 沒有插入成功，那麼 \(x\) 必定在異或一些數後變成了 \(0\)
就有 \(d[i]\ xor\ d[j]\ xor\ d[k]…xor\ x=0\)
也就是 \(d[i]\ xor\ d[j]\ xor\ d[k]…=x\)
如果 \(x\) 插入成功
則 \(d[i]\ xor\ d[j]…xor\ x=d[k]\)
變一下就是 \(d[i]\ xor\ d[j]\ xor\ d[k]…=x\)
對於性質二
如果 \(d[i]\ xor\ d[j]\ xor\ d[k]=0\)
那麼較晚插入的那一個一定會被異或成 \(0\)，不會插入線性基
對於性質三
目前不會證，建議看這篇部落格
用途
\(1\)、查詢 \(n\) 個數異或的最大值。
從高位到低位貪心地選，如果異或當前位的線性基後答案變得更大就異或上，否則就不選
程式碼
void cx(){
long long ans=0;
for(rg int i=60;i>=0;i--){
if((ans^d[i])>ans) ans^=d[i];
}
printf("%lld\n",ans);
}
\(2\)、查詢 \(n\) 個數異或的最小值。
就是線性基中最小的值
如果有插入不成功的情況，答案就是 \(0\)
\(3\)、查詢某個數是否能被異或得到。
看一下這個數能否成功插入線性基
如果可以，就能被異或得到，否則不能
\(4\)、查詢 \(n\) 個數異或的 \(k\) 小值
首先，要對這個序列的線性基處理一下，對於每一個 \(d[i]\) ，
枚舉 \(j=i \to 1\)，如果 \(d[i]_{(2)}\) 的第 \(j\) 位為 \(1\)
那麼 \(d[i]\ xor\ d[j-1]\)
其實就是讓每一個線性基提供自己最高位上的一
這樣，我們只需要把 \(k\) 進行二進位分解，貪心去選即可
異或之後得到的數組仍然是一個線性基
也就是說一個序列的線性基不唯一，只是元素數量唯一而已
題目
利用了性質三，貪心地選擇
同樣利用了性質三
線性基可以支援 \(RMQ\)
