前置知識：矩陣、高斯消元

行列式

行列式定義

\[\text{det(A)}=\sum_{p}{(-1)^{\mathrm{sgn}(p)}\prod{A_{i,p_i}}} \]

其中 \(\text{sgn}(p)\) 表示排列 \(p\) 的逆序?qū)€數(shù)。

行列式性質(zhì)

• 進(jìn)行一次矩陣轉(zhuǎn)職，行列式不變。(易證)
• 行列式任意一行按比例擴(kuò)大，行列式的值按同樣比例擴(kuò)大。(易證)
• 行列式中交換任意兩行，行列式反號。(易證)
• 行列式中若有兩行成比例，則行列式值為 \(0\)。(通過第二條證明)
• 行列式中若有一行可以表示為兩個數(shù)列相加，則行列式為兩個行列式的值的和。(證明如下)

\[\text{det}(A)=\sum_p(-1)^{\mathrm{sgn}(p)}\times(B_{k,p_k}+C_{k,p_k})\times \prod_{i=1}^{n~\text{and}~i\not=k}{a_{i,p_i}}=\mathrm{det}(B)+\mathrm{det}(C) \]

行列式求值

P7112 【模板】行列式求值

根據(jù)上面五條性質(zhì)，可以將矩陣一步步消為左下角全是 \(0\) 的舉證，類似于高斯消元。最后將矩陣的對角線乘起來即可。

n=rd(),mod=rd(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=rd()%mod; for(int i=1;i<=n;i++) {for(int j=i+1;j<=n;j++){while(a[j][i]){ll tmp=a[i][i]/a[j][i];for(int k=i;k<=n;k++)a[i][k]=(a[i][k]-tmp*a[j][k]%mod+mod)%mod;swap(a[i],a[j]),w=-w;}} } for(int i=1;i<=n;i++) ans=ans*a[i][i]%mod; printf("%lld\n",(mod+w*ans)%mod);

LGV 引理(Lindstrom-Gessel-Viennot lemma)

LGV 引理 內(nèi)容

• \(G\) 是一個有限的帶權(quán)有向無環(huán)圖。每個頂點的度是有限的，不存在有向環(huán)(所以路徑數(shù)量是有限的)。
• 起點 \(A=\{a_1,\cdots,a_n\}\)，終點 \(B=\{b_1,\cdots,b_n\}\)。
• 每條邊 \(e\) 有邊權(quán) \(\omega_e\)。
• 對于一個有向路徑 \(P\)，定義 \(\omega(P)\) 為路徑上所有邊權(quán)的積。
• 對任意頂點 \(a,b\)，定義 \(e(a,b)=\sum\limits_{P:a \to b}{\omega(P)}\)，所有 \(a\) 到 \(b\) 的路徑的 \(\omega\) 之和。

設(shè)矩陣

\[M={\begin{pmatrix}e(a_{1},b_{1})&e(a_{1},b_{2})&\cdots &e(a_{1},b_{n})\\e (a_{2},b_{1})&e(a_{2},b_{2})&\cdots &e(a_{2},b_{n})\\\vdots &\vdots &\ddots &\vdots \\e(a_{n},b_{1})&e(a_{n},b_{2})&\cdots &e(a_{n},b_{n})\end{pmatrix}} \]

從 \(A\) 到 \(B\) 的不相交路徑組 \(P=(P_1,P_2,\cdots,P_n)\)，\(P_i\) 表示從 \(a_i\) 到 \(b_{\sigma(i)}\) 的一條路徑，其中 \(\sigma\) 是一個排列(反映了這個排列的映射關(guān)系)，并且滿足對任意 \(i\not=j\)，\(P_i\) 與 \(P_j\) 沒有公共點。記 \(\sigma(P)\) 表示 \(P\) 對應(yīng) \(B\) 的排列。

引理說明，\(M\) 的行列式是所有從 \(A\) 到 \(B\) 的不相交路徑 \(P=(P_1,\cdots,P_n)\) 的帶符號和。

\[\mathrm{det}(M)=\sum_{P:A\to B}{(-1)^{\mathrm{sgn}(\sigma(P))}\prod_{i=1}^{n}\omega(P_i)} \]

證明

反證法，即只需證明：(其中 \(P:A\rightarrow B\)，存在 \(i\not=j\)，\(P_i\) 與 \(P_j\) 有交點)

\[\mathrm{det}(M)=\sum_{P:A\rightarrow B}(-1)^{\mathrm{sgn}(\sigma(P))}\prod_{i=1}^{n}{\omega(P_i)}=0 \]

假設(shè)存在一個 \(P\)，其中 \(P_i\) 與 \(P_j\) 相交，則 \(a_i\rightarrow b_{\sigma(i)}\) 與 \(a_j\rightarrow b_{\sigma(j)}\) 相交。那么我們將 \(b_{\sigma(i)}\) 與 \(b_{\sigma(j)}\) 互換，最后答案不變而奇偶性相反，一定存在 \(P'=-P\)。因此，如果這一組路徑有交點，那么一定被抵消，原命題得證。

應(yīng)用

P6657 【模板】LGV 引理

由于在網(wǎng)格上，如果 \(\sigma\not=(1,2,\cdots,n)\)，則顯然沒有解。

因此直接

\[\text{det}(M)=\sum_{P:A\rightarrow B}{1} \]

構(gòu)造矩陣，\(e(a_i,b_j)=\binom{b_j-a_i+n-1}{n-1}\) 后求行列式即可。

P7736 [NOI2021] 路徑交點

乍一眼好像就是 LGV 模型。

就是每一次的 \(\sigma(P)\) 變?yōu)榱嗣恳粚拥狞c對，但是發(fā)現(xiàn)最終的排列方式的逆序?qū)?shù)的奇偶性和中間怎樣連接沒有關(guān)系，所以可以直接 \((-1)^{\mathrm{sgn}(\sigma(P)}\)，似乎就做完了。

矩陣樹定理

咕咕咕

總結(jié)

以上是生活随笔為你收集整理的行列式、LGV、矩阵树学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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