矩陣

矩陣加法：

相同位置相加。

矩陣乘法：

滿(mǎn)足分配率、結(jié)合律，不滿(mǎn)足交換律(矩陣與逆矩陣之間除外) 。

矩陣轉(zhuǎn)置：

記矩陣為 \(A\) ，則 \(A\) 的轉(zhuǎn)置記為 \(A^T\) 。

性質(zhì)：

• \[{(A^T)}^T=A \]
• \[{(A+B)}^T=A^T+B^T \]
• \[{(k\times A)}^T=k\times A^T \]
• \[{(AB)}^T=A^TB^T \]

矩陣求逆：

P4783 【模板】矩陣求逆

\[\begin{bmatrix}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{bmatrix} \]

對(duì)左半邊的矩陣做高斯消元，同時(shí)更新右半邊的部分，(交換時(shí)也一起交換，但最終不用再換回來(lái)了)。而做完之后的右半邊部分就是求得的逆矩陣。

矩陣快速冪：

• 對(duì)于不含常數(shù)項(xiàng)的遞推式：(比較正常的矩陣快速冪)

• 對(duì)于含有常數(shù)項(xiàng)的遞推式：加上一維，在轉(zhuǎn)移矩陣中不更改。

• 對(duì)于含有關(guān)于 \(n^1\) 的遞推式：加上兩維，每次后一位給前一位加一。

• 對(duì)于含有關(guān)于 \(n^k\) 的遞推式：加上 \(k+1\) 維，例：

\[f[n]=2\times f[n-1]+n^k \]\[\Downarrow \]\[\begin{bmatrix}s[n]&n^k&n^{k-1}&\cdots&n^0\end{bmatrix}\times\begin{bmatrix}2&0&0&0&\cdots&0\\C_k^0&C_k^0&0&0&\cdots&0\\C_k^1&C_k^1&C_{k-1}^0&0&\cdots&0\\C_k^2&C_k^2&C_{k-1}^1&C_{k-2}^0&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\C_k^k&C_k^k&C_{k-1}^{k-1}&C_{k-2}^{k-2}&\cdots&C_0^0\end{bmatrix}=\begin{bmatrix}s[n+1]&{(n+1)}^k&{(n+1)}^{k-1}&\cdots&{(n+1)}^0\end{bmatrix} \]

注意：！！

由于轉(zhuǎn)移矩陣與答案舉證的大小不同，應(yīng)該在 struct 的矩陣中記錄這個(gè)矩陣的大小，防止將 \(O(n^2)\) 變?yōu)?\(O(n^3)\) ！！！

高斯消元

復(fù)雜度(樸素)： \(O(n^3)\)

主要代碼：

scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++) scanf("%lf",&a[i][j]); for(int i=1,Max=1;i<=n;Max=++i) {for(int s=i+1;s<=n;s++) if(fabs(a[s][i])>fabs(a[Max][i])) Max=s; // 找出絕對(duì)值最大的 for(int j=1;j<=n+1;j++) swap(a[i][j],a[Max][j]);if(a[i][i]<10e-8 && a[i][i]>-10e-8) { p=false; break; } // 記得 double 的精度問(wèn)題 for(int s=1;s<=n;s++) if(s!=i) // 這樣省去了第二步處理的麻煩 {double tmp=0-(a[s][i]/a[i][i]);a[s][i]=0;for(int j=i+1;j<=n+1;j++) a[s][j]+=tmp*a[i][j];} } if(p) for(int i=1;i<=n;i++) printf("%.2lf\n",a[i][n+1]/a[i][i]); else printf("No Solution\n");

線性基

線性基為一個(gè)數(shù)集構(gòu)造出來(lái)的新數(shù)集，滿(mǎn)足以下性質(zhì)：

• 線性基的元素能相互異或得到原集合的元素的所有相互異或得到的值。

• 線性基是滿(mǎn)足性質(zhì) \(1\) 的最小的集合。

• 線性基沒(méi)有異或和為 \(0\) 的子集。

• 線性基中不同的異或組合異或出的數(shù)都是不一樣的。

• 線性基中每個(gè)元素的二進(jìn)制最高位互不相同。

用處：

• 快速查詢(xún)一個(gè)數(shù)是否可以被一堆數(shù)異或出來(lái)

• 快速查詢(xún)一堆數(shù)可以異或出來(lái)的最大 \(/\) 最小值

• 快速查詢(xún)一堆數(shù)可以異或出來(lái)的第 \(k\) 大值

處理線性基：

void Insert(ll x) {for(int i=62;i>=0;i--){if(!(x & (1ll<<(ll)i))) continue; // 防止對(duì)高位影響 if(!p[i]) { p[i]=x; break; }x^=p[i]; // 更新 [0,i-1] 位的更優(yōu)答案 }if(!x) zero=1ll; // 特判 0 }

查詢(xún)一個(gè)元素是否可以被異或出來(lái)：

bool ask(ll x) {for(int i=62;i>=0;i--) if(x&(1ll<<(ll)i)) x^=p[i];return x==0; }

查詢(xún)異或最大值：

ll query_max() {ll ret=0;for(int i=62;i>=0;i--) if((ans^p[i])>ans) ans^=p[i];return ans; }

查詢(xún)異或最小值：

ll query_min() {for(int i=0;i<=62;i++) if(p[i]) return p[i];return 0; }

查詢(xún)異或第 \(k\) 小：

void rebuild() {// 重建 d 數(shù)組，求出哪些位可以被異或?yàn)?1// d[i] 只有第 i 個(gè)二進(jìn)制位為 1 for(int i=62;i>=1;i--) // 從高到低防止后效性 for(int j=i-1;j>=0;j--)if(p[i] & (1ll<<(ll)j)) p[i]^=p[j];for(int i=0;i<=62;i++) if(p[i]) d[cnt++]=p[i]; } ll kth(ll k) {if(!k) return 0ll; // 特判 0 if(k>=(1ll<<(ll)cnt)) return -1ll; // k 大于可以表示出的數(shù)的個(gè)數(shù) ll ret=0;for(int i=62;i>=0;i--) if(k & (1ll<<(ll)i)) ret^=d[i];return ret; }

變式：

O(logn) 求區(qū)間異或最大值：

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

題意：給定一棵樹(shù)，求 \(x\) 到 \(y\) 路徑的異或最大值。

用 \(p[x][]\) 表示點(diǎn) \(x\) 到根之間所有點(diǎn)的線性基，同時(shí)維護(hù) \(pos[x][]\) 表示這一線性基由哪一個(gè)點(diǎn)轉(zhuǎn)移而來(lái)。

在 \(\text{Dfs}\) 加入一個(gè)新的點(diǎn)時(shí)，貪心將貢獻(xiàn)相同或更高，且深度更大的點(diǎn)代替原來(lái)線性基中的值。

這樣查詢(xún)的時(shí)候就能在 \(O(\log_{2} n)\) 復(fù)雜度內(nèi)求出在點(diǎn) \(x\) 到 \(Lca\) 路徑中的點(diǎn)的最大異或和(更深的點(diǎn)已經(jīng)加入線性基)。

完整代碼

CF1100F Ivan and Burgers

題意：求出序列中 \(l\) 到 \(r\) 的區(qū)間最大異或和。

和上一題差不多，將維護(hù)更深的點(diǎn)轉(zhuǎn)化為維護(hù)更靠后的點(diǎn)即可。

完整代碼

線性基還可以推廣至非二進(jìn)制的情況。

P3265 [JLOI2015]裝備購(gòu)買(mǎi)

這里需要維護(hù)一個(gè) \(k\) 進(jìn)制的線性基

主要代碼：

int p[Maxn]; // 由于浮點(diǎn)數(shù)存儲(chǔ)不方便，這里 p 記錄的是值的下標(biāo) struct Data {ld val[Maxk];int Cost; }a[Maxn]; void Insert(Data k) // 這里傳入的也是下標(biāo) {for(int i=1;i<=m;i++){if(fabs(a[k].val[i])<10e-8) continue;if(!p[i]) { p[i]=k,cnt+=1,sum+=a[k].Cost; break; }ld tmp=a[k].val[i]/a[p[i]].val[i];for(int j=i;j<=m;j++) a[k].val[j]-=a[p[i]].val[j]*tmp;} }

較復(fù)雜的情況

P4151 [WC2011]最大XOR和路徑

總結(jié)

以上是生活随笔為你收集整理的线性代数（矩阵、高斯、线性基……）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。