基本概念

矩陣乘法

基本概念

對于一個 \(n\times p\) 和 \(p\times m\) 的矩陣做矩陣乘法可以得到一個 \(n\times m\) 的矩陣。

矩陣乘法具有結合律，但是沒有交換律。其中結合律為我們用線段樹或者倍增之類的結構維護矩陣乘法提供了依據。

優化 DP 的時候可以看成貢獻系數，比如對于 \(f\to g\) 的單維度轉移，也就是兩個向量之間的轉移，可以用向量乘以矩陣得到向量來求解。對于 \(i\to j\) 的轉移，其系數就是矩陣中的 \((i,j)\) 位置上的數。常用于動態 DP 的求解。

應用

P7453 [THUSC 2017] 大魔法師（線性變換）

假設我們現在有一個向量 \(\vec{A}\)，我們想將其變成 \(\vec {A'}\)。

數字是瞎寫的，但是體現了線性變換的過程。線性變換可以用矩陣來刻畫。如果有賦值操作和加一個常數的操作，就需要我們給向量手動多開一個常數維度，初始為 \(1\) 就行了。

根據 \(A\times B\to A'\)，可以得到 \(A'_k\gets A_j\times B_{j,k}\)。所以 \(B_{i,j}\) 就是 \(A_i\) 對于 \(A'_j\) 的貢獻系數。

本題設計出矩陣之后，直接使用線段樹維護矩陣就行了。

P10102 [GDKOI2023 提高組] 矩陣

判定取模意義下的矩陣乘法結果是否成立。暴力矩陣乘法的時間復雜度是立方的會超時。

考慮隨機一點的東西，我們對于等式兩邊都左乘一個相同的隨機向量，這樣子向量乘以矩陣是 \(O(n^2)\) 的。

這是一個必要不充分條件，但是失敗的概率小于 \(\dfrac{1}{P}\)。

P6569 [NOI Online #3 提高組] 魔法值（輔助 DP 轉移）

圖上階段數很大的轉移，考慮用 DP 值構成的向量去乘以帶著貢獻系數的鄰接矩陣。

詢問的時候如果直接矩陣快速冪是 \(O(qn^3\log V)\)，提前處理 \(2^i\) 的鄰接矩陣自己乘自己，然后詢問的時候拿向量來乘矩陣之后每次得到的都是向量，向量乘以矩陣是平方的，單次乘法的復雜度少一個 \(n\)，就是 \(O(qn^2\log n)\) 了。

QOJ10520. 矩陣除法（模 2 意義下的矩陣求逆）

太深刻了，考慮矩陣乘法的本質，就是 \(A\to C\) 的一個變換，其中加權系數矩陣為 \(B\)。

行間獨立，也就是 \(A\) 的第 \(i\) 行轉移到 \(C\) 的第 \(i\) 行，至于這一行內每一列的權值，那就是行內加權了，加的權重為 \(B\) 的行內的值，\(B\) 的列表示對于 \(C\) 的每一列其在自己行內的加權系數相同。

那么轉化為 \(01\) 形態的矩陣，就是是否選擇了。\(B\) 的每一列獨立，考慮對于列單獨做，\(B\) 的每一列的若干個數就是最終 \(C\) 那一列的加權。

于是 \(B\) 某一列代表的就是從 \(A\) 中選擇若干列，他們異或起來等于 \(C\) 中的某一列。

使用線性基即可，再用 std::bitset 優化可以做到 \(O(\dfrac{n^3}{w})\)。

QOJ6504. Flower's Land 2（逆矩陣的應用）

首先有一個很重要的觀察，兩個位置在最后如果能被消除，那么一定奇偶性不同。

考慮非修改版本，在 \(i=2k\) 的位置放上 \(s_{a_i}\)，在 \(i=2k+1\) 的位置放上 \(s_{a_i}^{-1}\)，一個區間能被消除需要滿足其矩陣乘法之后的結果為單位矩陣。

考慮帶上修改，發現不管怎么加，一個節點的可能形態只有 \(3\) 種，也就是區間加 \(0,1,2\) 之后的矩陣，我們維護加法 tag，根據目前的形態切換該節點的矩陣即可。

時間復雜度 \(O((n+q)\log n)\)。

行列式

基本概念

• 記作 \(\det(A)\) 或者 \(\lvert A\rvert\)。

求值：\({\rm det}(A)=\sum\limits_p (-1)^{f(p)}\prod A_{i,p_i}\)，其中 \(f(p)\) 為 \(p\) 的逆序對數，\(p\) 取遍 \(1\sim n\) 的排列。

如果沒有 \(-1\) 的系數就是積和式了，但是目前無多項式復雜度求解。

性質

• \(\lvert I\rvert=1\)

• 上三角（右上）矩陣的值為主對角線乘積。（求解行列式的基礎）

• 交換矩陣兩行，行列式變號

• 矩陣乘上一常數，行列式也相應乘上一常數

• 當矩陣有兩行相等或者呈倍數關系，行列式為 \(0\)。

• 若兩矩陣至多一行不相等，則將這一行相加所得矩陣的行列式為原來兩個之和。

• 矩陣某一行加上另一行倍數，行列式不變。

例題

P7112 【模板】行列式求值

  while(a[i][i]){
  	int p=a[j][i]/a[i][i];
  	for(int k=i;k<=n;k++) a[j][k]=(a[j][k]-1ll*p*a[i][k]%mod+mod)%mod;
  	swap(a[i],a[j]); t*=-1;
  }
  swap(a[i],a[j]); t*=-1;

如果模數不是質數的話，使用輾轉相除法。

利用初等變換將矩陣變成上三角矩陣，然后值就是對角線乘積。

注意細節如果交換兩行，需乘以 \(-1\)。

P6113 【模板】一般圖最大匹配

咕咕咕，以后再補。先放一個鏈接

想不到吧，這種圖論難題也存在線性代數做法。

考慮隨機生成一個數組 \(a_{i,j}\) 滿足 \(a_{i,j}=a_{j,i}\)。假如存在邊 \((i,j)\)（\(i<j\)），我們就在 \((i,j)\) 位置填上 \(a_{i,j}\)，且在 \((j,i)\) 填上 \(-a_{j,i}\)。

Tutte 定理：如果圖存在完美匹配，當且僅當 \(\det(A)\neq 0\)。

證明就是先證明圖存在完美匹配當且僅當可以用若干偶環（包括二元環）來覆蓋整張圖。

對于奇偶環討論一下，然后會消掉的。

推論是最大匹配數就是 \(\dfrac{\mathrm{rank(A)}}{2}\)，高斯消元可解。

其中隨機數 \(a_{i,j}\in [0,P-1]\)，在模 \(P\) 的意義下求解。

對于多項式 \(\sum a_ix^i\equiv 0\pmod P\)，錯誤率是 \(\dfrac{n}{P}\)。

同時，我們還需要構造方案。

高斯消元

P4783 【模板】矩陣求逆

\(A^{-1}A=I\)，將矩陣乘法看成線性變換。

對于 \(A\) 做一個 \(A^{-1}\) 的線性變換可以得到 \(I\)，對于 \(I\) 做一個 \(A^{-1}\) 的線性變化可以得到 \(A^{-1}\)。

注意到 \(A\) 和 \(I\) 的線性變化過程是相同的（都是 \(A^{-1}\)），所以我們在對于 \(A\) 線性變換成 \(I\) 的時候，對于 \(I\) 做同樣的操作，就可以把 \(I\) 變成 \(A^{-1}\)，也就得到了 \(A^{-1}\)。很巧妙吧。

P3389 【模板】高斯消元法

消成上三角矩陣之后，倒著一行一行求解。時間復雜度 \(O(n^3)\)。

P2455 [SDOI2006] 線性方程組

加入了對于無解和無數解的判斷，有點小麻煩。兩者的主要區別就在于左側系數為 \(0\) 的時候，右側是否為 \(0\)。

無數解就是系數為 \(0\)，等號另一側也為 \(0\)。無解就是系數為 \(0\)，等號另一側不為 \(0\)。

需要注意的是如果遇到有一個無解那么肯定整體無解，但是如果遇到有一個無數解，那么也可能最終無解，所以需要處理所有方程。當我們在處理過程中遇到所有 \(x_i\) 的系數都為 \(0\) 的時候就跳過去去處理 \(x_{i+1}\)，可以采用 \(cnt\) 記錄已處理方程數，對于每個主元 \(x_i\) 對編號在 $ > cnt$ 之后的所有方程進行操作，而非對于 \(\ge i\) 的。這樣最后剩下的 \([cnt+1,n]\) 即為各項系數全部為 \(0\) 的方程，判斷一下即可。

P4035 [JSOI2008] 球形空間產生器

解多元二次方程題，可得到對于 \(\forall i \in [1,n+1]\)， \(\sum\limits_{j=1}^n(x_j-c_{i,j})^2=R^2\)
展開可得 \(\sum\limits_{j=1}^n x_j^2-2x_jc_{i,j}+c_{i,j}^2=R^2\)

觀察一下形式，有平方項顯然不太好處理，注意 \(c_{i,j}\) 為已知，所以這個無需處理。我們發現 \(R\) 與題無關顯然不用求，于是考慮相鄰兩個式子作差，\(x_j^2\) 平方項以及 \(R^2\) 就消掉了。直接高斯消元即可。

P2447 [SDOI2010] 外星千足蟲

加法同余式轉化為異或方程組，可得：

注意這里是貪心最少的方程個數，所以方法就是盡可能在前面幾個方程里面找就行了。
可以用 bitset 快速消元，時間復雜度 \(O(\dfrac{n^3}{w})\)。

矩陣樹定理

將度數矩陣和鄰接矩陣作差之后任意去掉一行求行列式。

• 無向圖

記 \(D_{i,j}=\begin{cases} deg_i&i=j \\0&i\neq j \end{cases}\)
\(A_{i,j}=e_{i,j}\) (其中 \(e_{i,j}\) 代表 \(i \to j\) 重邊數量)。
于是得到 \(L=D-A\)，將 \(L\) 去掉第 \(i\) 行和第 \(i\) 列，其中 \(i\) 任選，得到的矩陣求行列式即可。

• 有向圖

對于有向圖就是把度數矩陣改為入度或者出度，根據要求的外向樹還是內向樹來決定使用入度還是出度。同時去掉的那一行和一列必須為 \(root\)。注意外向樹答案為入度統計，而內向樹是出度統計。

可以廣義擴展一下，其實就是所有樹邊多項式乘積之和。

P6178 【模板】Matrix-Tree 定理

當生成樹邊權為所有邊的乘積的時候，直接將邊權改為重邊即可。

P6624 [省選聯考 2020 A 卷] 作業題

等學完了莫比烏斯反演在來寫這題。

P4336 [SHOI2016] 黑暗前的幻想鄉

P3317 [SDOI2014] 重建

P10881 「KDOI-07」能量場

P5807 【模板】BEST 定理 | Which Dreamed It

\(1\) 為起點，除了起點，其他點的最后一條出邊不形成環，所以所有最后一條出邊就是以 \(1\) 為根的內向樹，欽定完了最后一條出邊之后，剩下的邊以任意順序訪問，是一個階乘的形式。

因此有向圖的歐拉回路個數：\(\prod\limits_u(deg_u-1)!\times\) 以某點為根的內向樹個數

注意上述定理情況是沒有指定根的情況，其去掉了循環同構。如果固定了起點 \(s\) 的話，就是 \(deg_s!\) 了，所以我們需要額外 \(\times deg_1\)。

注意特判掉不存在歐拉回路，對于孤立點我們對其打一個標記，然后求行列式之類的時候跳過它即可。求生成樹個數直接套用 Matrix-Tree 定理即可。

線性基

給定一組向量 \(\{ \vec{a_i} \}\)，求他們的一組基底 \(\{ \vec{b_i} \}\) 使得任意一個 \(a_i\) 都可以通過 \(b_j\) 線性組合出來。

在 OI 范圍內的應用一般是二進制異或線性基。

P3265 [JLOI2015] 裝備購買

向量版本的線性基。

我們每次不斷插入向量，從高位到低位來判斷，如果該維度沒有，那就用當前向量表示，否則把當前向量的當前維度使用之前在這一位的基來消為 \(0\)，然后做下一維度。

P3421 [POI2005] SKO-Knights

即求 \(n\) 個二維向量的大小為 \(2\) 的線性基。

注意不同于上一題中的實系數，本題是整系數，整系數除法不具有可逆性，所以我們只能用加減法。

我們維護線性基內的兩個向量 \(\vec{a},\vec\)，考慮加入一個向量 \(\vec{c}\)，在我們對于 \(\vec{a},\vec\) 在 \(x\) 這一維上進行輾轉相減，對于 \(\vec{a},\vec{c}\) 也在 \(x\) 這一維度上輾轉相減，然后令 \(y_b\gets \gcd(y_b,y_c)\) 即可。

P3812 【模板】線性基

每次插入一個數 \(x\)，從高位到低位遍歷二進制位。

如果該位沒有 \(1\) 就跳過，否則查看這位有沒有代表元 \(p_i\)，如果沒有就把這個數設置為這一位的代表元。如果有了，就令 \(x\gets x\operatorname{xor} p_i\)，然后繼續往后遍歷。

對于 \(\min,\max\) 和能否被表示都是簡單的。

現在考慮排名之類的問題。需要重構線性基。

`

void rebuild(){
	cnt=0; memcpy(q,p,sizeof(p));
	for(int i=60;i>=0;i--)
		for(int j=i-1;j>=0;j--)
			if((p[i]>>j)&1) q[i]^=q[j];
	for(int i=0;i<=60;i++) 
		if(p[i]) d[++cnt]=q[i];
}

`

就是把各位獨立。

CF1100F Ivan and Burgers

區間線性基模板題。

對于每一個前綴 \(r\) 建立前綴線性基，貪心地保留影響該位的最大的 \(l\) 即可。

注意更換之后原先的可以拿過去更新后面。

CF1902F Trees and XOR Queries Again

思想同上一題。維護最深的點，然后合并兩個線性基即可，要求是所選的點深度必須 \(\ge dep_{\operatorname{lca(x,y)}}\)。

P11713 [清華集訓 2014] 瑪里茍斯

首先，第一步觀察就是你可以直接將 \(S\) 替換為 \(S\) 的線性基。雖然不改變能異或出來的數，但是會不會影響方案數導致期望變了？其實是不會的，設線性基大小為 \(\rm dim(V)\)，因為線性基內部的元素可以支配最后的異或值，所以任何一個能被表示出來的數，其在線性基外面每個數都可以隨便選或者不選，方案數為 \(2^{n-\rm dim(V)}\) 都是相同的，線性基內部每個數是否被選擇就就唯一確定了，方案數為 \(1\)。故每個數方案數相同，直接換成線性基之后還是方案數相同。

于是我們要求的就是線性基中所有能被表示出來的 \(x\)，對其 \(x^k\) 之后求平均值。將 \(x\) 進行二進制拆分，\(x=\sum\limits_{i=0}^{\log x}b_i2^i\)，其中 \(b_i\in \{0,1\}\)。\((\sum\limits_{i=0}^{\log x}b_i2^i)^k\) 的組合意義就是從所有二進制位中可重復地選擇 \(k\) 個二進制位，把他們的大小相乘之后對于所有方案求和。

直接暴力枚舉選擇哪 \(k\) 個的復雜度是 \(\log^k V\)，可以接受。問題是我們現在手頭上并沒有具體的線性基能表示出來的數字的集合，一共有 \(2^{\rm dim(V)}\) 種數也不可能全部都枚舉出來，這個量非常大。

于是我們先枚舉這 \(k\) 個二進制位求出乘積之后算有多少種從線性基中選擇數的方案使得其可以包含這 \(k\) 個二進制位。然后用乘積乘以方案數累加進答案。由于是期望所以最后要乘以 \(\dfrac{1}{2^{\rm dim(V)}}\)。

為了包含這 \(k\) 個二進制位，我們再次對于這 \(k\) 個二進制位（離散化為 \([0,k-1]\)）建立線性基來求方案數。設新的線性基大小為 \(\dim(V')\)，那么最后包含這 \(k\) 個二進制位的方案數就是 \(2^{\rm dim(V)-\rm dim(V')}\)，除以 \(\rm dim(V)\) 之后，貢獻系數就是 \(2^{-\rm dim(V')}\)。最后乘上 \(k\) 個二進制位的乘積即可。

還有一個問題就是精度不會爆掉嗎？可以發現唯一出現小數的地方是 \(2^{-\rm dim(V')}\) 這個地方，假設選擇的 \(k\) 個二進制位中不同的位子的個數為 \(m\)。那么 \({\rm dim}(V')\le m\)，一個進制位 \(i\) 會貢獻 \(2^i\)，所以除非 \(i=0\)，否則絕大部分情況都是會至少抵消甚至貢獻更多的 \(2\)。只有當 \(m=1\)，\(i=0\) 或者 \(m=2,i\in \{0,1\}\) 的時候才會出現 \(\dfrac{1}{2}\) 的系數，這個好處理，我們先給答案乘以 \(2\)，最后再判斷奇偶性看看是否需要加上 \(0.5\) 即可。

時間復雜度為 \(O(k\log^{k+1} V)\)。

CF1336E2 Chiori and Doll Picking

LGV 引理

雜題

CF1603F October 18, 2017