線性基很好理解，可以理解成 \(n\) 維的向量。

我們先考慮 \(n=2\)，這是我們最熟悉的，可以在平面直角坐標系上表示出來。

眾所周知，在一個平面內，兩個不共線的向量 \(e_1\) 和 \(e_2\)，可作為基底，即所有可在原坐標系上表示的向量 \(x\) 均可被 \(e_1\) 和 \(e_2\) 表示為 \(\lambda e_1 + \mu e_2 (\lambda,\mu \in R)\)，\(n\) 維向量以此類推。

而這個基底，也就是基。

這是一種很膚淺的理解，但我們也算是對線性基有了一些了解。接下來就是較為具體的敘述。

基（也稱為基底）是描述、刻畫向量空間的基本工具，剛剛的 \(e_1\) 和 \(e_2\) 就可以將“所有向量”表示出來，這個 “所有向量”，就是向量空間，只不過這個向量空間是無窮大的而已。

那如果給你一個有限的向量空間 \(S\)，那么基就是 \(e=\left\{ e_1,e_2,...,e_k \right\}\)，其中滿足這組基能夠表示這個向量空間 \(S\)，那也就可以表示成 $\mathrm{span}(e) $，那么這組基需要滿足 \(\forall_i,e_i \notin \mathrm{span}(\frac{e}{e_i})\)（即互相不能表示），而且，根據上文，容易發現 \(n\) 維向量空間的基最多有 \(n\) 個。

接下來就是如何求出一組基

所以對于現在的基的集合，我們記為 \(E\)，我們枚舉當前向量 \(x=(a_1,a_2,...,a_n)\)，看是否在 \(\mathrm{span}(E)\) 中。

這其實就是一個消元的過程，我們先令 \(E\) 中的元素 \(E_i\) 為第 \(1\) 個非 \(0\) 的位置是 \(i\) 的向量，然后我們按維數從低往高考慮，嘗試將當前維刪到 \(0\) 即可，若當前維不存在基，那就將現在的向量加入 \(E\) 中。

OI 中用的最多的是異或線性基，以下是一些應用：

1.插入操作

void insert(int x){
	for(int i=N-1;i>=0;i--){
		int p=x>>i;
		if(!p) continue;
		if(!bas[i]){
			bas[i]=x;
			s++;
		}
		x^=bas[i];
	}
}

2.最大異或和 & 第 \(k\) 大異或和

最大異或和是簡單的，從高位往低位考慮即可

int qmax(){
	int res=0;
	for(int i=N-1;i>=0;i--) res=max(res,res^bas[i]);
}

第 \(k\) 大只需稍作修改，不再贅述

3.線性基合并

這個也是容易的，就是將其中一個線性基中的基拿出來 insert 到另外一個即可。

復雜度 \(log^2(V)\)。(\(V\) 是值域)

4.線性基求交

求交的意思是求兩個線性基的線性空間（可以想成向量空間） \(V_a = \mathrm{span}(a)\) 和 \(V_b = \mathrm{span}(b)\) 的交的基。

發現不太好直接通過線性基 \(a\) 和 \(b\) 直接求，但我們容易知道 \(b\) 中有那些基是能夠被 \(a\) 表示出來的，形式化來講，就是 \(U = \left \{i|b_i \in V_a \right \}\)。那么顯然有 \(\mathrm{span}(U) \subseteq V_a \wedge V_b\)。

那如果 \(a \cup \frac{U}\) 線性無關，就有 \(\mathrm{span}(U) = V_a \wedge V_b\)。

證明：考慮有一個值 \(v\) 不能被 \(U\) 表示，但是在 \(V_a \wedge V_b\) 中。那么 \(\frac{U}\) 中的元素一定會參與，設參與了的值的異或和為 \(t\)，那么顯然 \(v \oplus t\) 能被 \(a\) 表示出來，因為 \(U\) 中的值均在 \(V_a\) 中，但是 \(a\) 本身就能表示 \(v\)，而 \(a \cup \frac{U}\) 也可以表示出 \(v\)，且兩種表示方法顯然不同，但我們又知道一個值在一個線性無關組中并不存在 \(2\) 種不同的表示方法，\(Q.E.D\)。

所以我們只需把 \(a \cup \frac{U}\) 給調整成線性無關的即可。也就是說找到一組合適的 \(b\) 滿足以上條件。

首先先有一個直接按照上面所說的，枚舉當前 \(b_i\)，看當前 \(a \cup \frac{U}\) 是否能將 \(b_i\) 表示出來，如果不可以，就將其加入 \(\frac{U}\)。不然，我們設 \(x\) 為參與表示 \(b_i\) 的 \(a\) 中的元素的異或和，我們將 \(x\) 加入 \(U\) 中。

但這個復雜度是 \(O(log^3 (V))\) 的，并不是很理想。

所以我們動態維護 \(a \cup \frac{U}\) 的三角線性基（也就是上面的 insert），在維護基的基礎上，再維護一個組成當前元素在 \(a\) 的部分的異或和，這樣就可以在 \(O(log^2(V))\) 的時間復雜度內實現了

int V=63;
node wedge(node X,node Y){
    for(int i=0;i<=V;i++){
        tmpb[i]=tmpc[i]=X.b[i],X.b[i]=0;
    }
    for(int i=V;i>=0;i--){
        if(!Y.b[i]) continue;
        ull x=Y.b[i],y=0;
        for(int j=V;j>=0;j--){
            if((x>>j)&1ull){
                if(!tmpb[j]){
                    tmpb[j]=x,tmpc[j]=y;
                    break;
                }
                x^=tmpb[j],y^=tmpc[j];
            }
        }
        if(!x) X.insert(y);
    }
    return X;
}

5.找到線性基能表示的數中比 \(x\) 大的最小值

首先先求得最大值，接著按位從大到小枚舉，如果當前位為 \(1\)，那就看異或上這個位置的基是否還比 \(x\) 大，如果仍比 \(x\) 大，那就異或上這個基。

int gt_greater(int x){
	int val=0;
	for(int i=29;i>=0;i--){
		if(!b[i]) continue;
		val=max(val,val^b[i]);
	}
	for(int i=29;i>=0;i--){
		if(!b[i]) continue;
		if(val>>i&1){
			if((val^b[i])>x) val^=b[i];
		}
	}
	return val;
}