Gauss-Jordan 求解逆矩陣。

行列式求值，其中 \(P\) 是排列，\(\pi(P)\) 是逆序對數。

另一種遞歸式定義：

注意到 gauss 消元后形成一個上三角矩陣，而該矩陣的行列式很好算，即 \(\prod a_{i,i}\)。由于 gauss 消元過程中都是初等行變換，考慮計算變換后行列式的變化。

• 交換兩行，行列式乘以 \(-1\)。
• 一行乘以 \(k\)，行列式乘以 \(k\)。
• 一行乘以 \(k\) 加到另一行，行列式不變。

int det(int n){
	int res=1;
	for(int i=2;i<=n;i++){
		int r=i;
		for(int j=i+1;j<=n;j++)if(a[j][i]>a[r][i])r=j;
		if(!a[r][i])continue;
		if(r!=i){
			res=-res;
			for(int j=i;j<=n;j++)swap(a[i][j],a[r][j]);
		}
		for(int j=i+1;j<=n;j++){
			while(a[j][i]){
				int d=a[i][i]/a[j][i];res=-res;
				for(int k=i;k<=n;k++)a[i][k]=mod(a[i][k]+p-(ll)d*a[j][k]%p),swap(a[i][k],a[j][k]);
			}
			//有逆時直接乘逆元也行 
		}
	}
	if(res<0)res+=p;
	for(int i=2;i<=n;i++)if(a[i][i])res=(ll)res*a[i][i]%p;
	return res;
}

LGV 引理。

Tutte 矩陣。

考慮設計矩陣 \(G\)。

對于 \(i\le j\)，如果 \(i\) 到 \(j\) 有邊，那么 \(G_{i,j}=x_{i,j}\)，\(G_{j,i}=-x_{i,j}\)。否則 \(G_{i,j}=G_{j,i}=0\)。

結論：\(\det(G)\ne 0\) 等價于圖存在完美匹配。

證明可以考慮 \(\det(G)\) 的定義

如果該式存在貢獻，那么對于 \(\forall i\)，\(i\) 到 \(p_i\) 必然有邊，產生貢獻的邊形成了若干個環。

注意到如果這些環中有奇環，那么把環翻轉后 \((-1)^{\pi(P)}\) 恰好取反，因此奇環的兩種情況抵消。

所以只需要考慮只有偶環的情況。此時每個偶環內的點必然存在匹配。而如果存在匹配，那么這些點兩兩成環必然合法。證畢。

考慮怎么求最大匹配，大膽猜測：答案是 \(\frac{rank(G)}{2}\)。證明忘了，時間復雜度 \(O(n^3)\)。

線性基

將長度為 \(n\) 的序列映射到長度為 \(\log V\) 的序列上。使其子集的異或集合相等。

可以 \(O(\log V)\) 插入，\(O(\log^2 V)\) 合并。通常解決子集異或問題，求 \(k\) 大的時候需要先通過線性變換使得任意 \(a,b\in S\) 滿足 \(a\oplus b\ge\max(a,b)\)。

通常搭配 \(O(1)\) 合并的數據結構如 st 表。

可刪線性基離線可做到 \(O(\log V)\)，記錄每個數的刪除時間，每次插入從高位到低位貪心地選擇最晚刪除的數。在線 \(O(\log^2 V)\)，https://www.luogu.com.cn/article/vd9qdrcd。

Matrix-Tree 定理

對于有向圖 \(G\)，定義

• 出度矩陣

  \[D^{\text{out}}_{i,j}(G)=\left\{\begin{matrix} \deg^{\text{out}}(i) & i=j \\ 0 & i\ne j \end{matrix}\right. \]

• 鄰接矩陣，設 \(\#e(i,j)\) 為 \(i\) 連向 \(j\) 的邊數。

  \[A_{i,j}(G)=\left\{\begin{matrix} 0 & i=j \\ \#e(i,j) & i\ne j \end{matrix}\right. \]

• 出度 Laplace 矩陣

  \[L^{\text{out}}(G)=D^{\text{out}}(G)-A(G) \]

入度類似。于是有以 \(k\) 為根的內向生成樹數量 \(t^{\text{root}}(G,k)\) 和外向生成樹數量 \(t^{\text{leaf}}(G,k)\) 為

相當于將第 \(k\) 行第 \(k\) 列去掉后行列式的值。

定義 \(m\times n\) 的關聯出度矩陣 \(M^{out}\) 為

同理得到關聯入度矩陣。

簡單推導可得 \(D^{out}=(M^{out})^{T}M^{out}\)，\(A=(M^{out})^TM^{in}\)。所以有 \(L^{out}=(M^{out})^T(M^{out}-M^{in})\)。

引理：

對于圖 \(G(V,E)\)，如果子圖 \(T(V,S)\) 是以 \(V\setminus W\) 為根的內向森林，當且僅當

通過分析可以知道，\(M^{out}_{S,W}\) 每行至多有一個 \(1\)，當 \(\det(M^{out}_{S,W})\ne 0\) 時即代表每行恰好一個 \(1\) 且每一列恰好一個 \(1\)，或者說 \(W\) 中每個點與 \(S\) 中一條邊的起點形成雙射，也可以說它們出度都為 \(1\)。

前半部分限制出度為 \(1\)，那么后半部分應該限制無環。當前面不為 \(0\) 時，\(M^{out}_{S,W}-M^{in}_{S,W}\) 每行每列恰有一個 \(1\)，但是可能有 \(1\) 或 \(0\) 個 \(-1\)。如果存在環，容易發現通過若干次一行加到另一行上最終會使得一行為 \(0\)，又由于該操作不改變行列式，故原行列式也為 \(0\)，如

并且當該式不為 \(0\) 時，可以通過該操作使得每行有且僅有一個 \(1\)，則此時 \(\det(M^{out}_{S,W}-M^{in}_{S,W})=\det(M^{out}_{S,W})\)。所以原式也 \(=\det(M^{out}_{S,W})^2=1\)。

Cauchy–Binet 公式：

對于 \(n\times m\) 的矩陣

聯立引理可證明矩陣樹定理，令 \(W=[n]\setminus\{k\}\)：

擴展

帶邊權。會發現實際上算的是所有生成樹邊權乘積的和。

因為將關聯矩陣重定義為

則引理算出來的行列式即為 \(\prod w_i\)。

求所有生成樹邊權和的 \(k\) 次方的和。

只需要把乘法變成加法，容易想到類似于原根的東西。

相當于將矩陣中的元素變成一個多項式，重定義加減乘除。對于本題來說，有

或者也可以理解為已知 \(w=w_1+w_2+\cdots w_{k-1}\) 的 \(0\sim k\) 次方，求 \((w+w_k)\) 的 \(0\sim k\) 次方。

答案就是 \(\det(k)\)。

應用

Cayley 公式

\(n\) 個點的完全圖生成樹數量為 \(n^{n-2}\)，寫出 Laplace 矩陣，用行列式知識可以得到。

Best 定理

對于一個有向歐拉圖，其不同歐拉回路的數量為

由于歐拉圖出度和入度相等，所以令 \(\deg(u)=\deg^{\text{out}}(u)=\deg^{\text{in}}(u)\)。只用考慮固定從 \(k\) 出發。

容易發現，由歐拉回路的性質，如果每個點除 \(k\) 外都取最后一條出邊，則會構成一棵樹。如果成環，意味著一個點在走完最后一條出邊后還走了它的入邊，顯然不會構成歐拉回路。

于是每條歐拉回路都能對應一棵以 \(k\) 為根的內向樹，除了樹上的邊外，其他邊的順序不固定，可以得到 \(t^{\text{root}}(G,k)\deg(k)!\prod_{u\in V,u\ne k}(\deg(u)-1)!\)，但是 \(k\) 會在路徑中出現 \(\deg(k)\) 次，所以一條路徑會計算 \(\deg(k)\) 次，去重后便得到上式。

可以感性理解方案與歐拉回路間構成雙射。