矩阵树定理(+行列式)

本文同时也作为`P6178`的题解。 # 1.行列式基础 - ## 行列式的定义 对于一个矩阵 $A[1...n][1...n]$ ,其行列式为 $\det(A)=\sum\limits_{P}(-1)^{\mu(P)}\prod\limits_{i=1}^nA[i][p_i]$ (枚举排列 $P[1...n]$ ,其中 $\mu(P)$ 为排列 $P$ 的逆序对数) ( $\det(A)$ 又作 $|A|$ ) 也就是说在每一**行**挑一个乘起来,然后再拿逆序对有关的东西做系数。 直接按照定义计算,复杂度是 $O(n!·n)$ 的。 - ## 行列式的性质 知道了下面几条性质之后,我们就能快速计算行列式了。 - (0) 单位矩阵 $I$ 的行列式为 $1$ 。 这个比较显然,因为 $P$ 除了对角线之外没有别的选择,而对角线乘积为 $1$。 类似的,上三角矩阵和下三角矩阵的行列式都是对角线乘积。 - (1) 交换矩阵的两行,行列式变号。 (根据逆序对感性理解即可) 我们考虑对于**每个排列**,这一次交换**只会**影响乘积组前面的逆序对系数。 对于任意一个序列,交换两个数对于逆序对个数的影响必定为**奇数**(可以自己讨论一下)。 所以逆序对系数全部都改变,即变号。 - (2) 若某一**行**乘以 $t$ ,行列式就也乘以 $t$ 。 这个比较好理解,因为这一行**选且只选**一个嘛。 - (3) 看公式: $\begin{vmatrix}a+a'&b+b'\\c&d\end{vmatrix}=\begin{vmatrix}a&b\\c&d\end{vmatrix}+\begin{vmatrix}a'&b'\\c&d\end{vmatrix}$ 还是因为一行选且只选一个,然后**乘法分配律**就好了。 (2,3合起来就是**行**的线性性) - (4) 有某两行一样的矩阵,行列式是 $0$. 这个证明比较巧妙 : 考虑交换相同的这两行,根据(1)得行列式**变号**。 但是矩阵并没有实质的改变,行列式**不变**,所以行列式的值只能是 $0$. - (5) 用矩阵的一行加上另一行的倍数,行列式不变。 考虑构造(**省略的部分表示不变**): 欲证$\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d+ka&e+kb&f+kc\end{vmatrix}$ 首先构造一个$\begin{vmatrix}a&b&c\\.&.&.\\a&b&c\end{vmatrix}$,根据(4)得其值为0. 又根据(2)得$\begin{vmatrix}a&b&c\\.&.&.\\ka&kb&kc\end{vmatrix}$也为0。 然后根据(3)得 $$\begin{vmatrix}a&b&c\\.&.&.\\d+ka&e+kb&f+kc\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}+\begin{vmatrix}a&b&c\\.&.&.\\ka&kb&kc\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}$$ - ## 消元求行列式 其实我们上面证明的性质,就是为这个来打基础的。 我们消元的时候,只是用了 {交换两行, 某一行乘一个常数, 一行加上另一行的倍数} 三种操作。 那么,我们对于 $A$ 进行消元,然后记录操作对于行列式的影响,最后得到上三角矩阵,行列式就是对角线乘积,如果消不出来那么返回 $0$。 最后再把影响逆回去即可。 # 2.矩阵树定理与部分扩展 (默认图中**无自环**) - ## 经典 给出一个无向无权图,设 $A$ 为邻接矩阵, $D$ 为度数矩阵( $D[i][i]=$节点 $i$ 的度数,其他的无值)。 则基尔霍夫(Kirchhoff)矩阵即为 : $K=D-A$ 然后令 $K'$ 为 $K$ 去掉**第k行与第k列**(k任意)的结果($n-1$阶主子式), $\det(K')$ 即为该图的生成树个数。 ~~证明不会。感兴趣的同学可以自行百度。~~ **例题** : [P4336 [SHOI2016]黑暗前的幻想乡](https://www.luogu.org/problemnew/show/P4336) - ## 加权扩展 容易理解 : 带重边的情况,上面的经典矩阵树定理也是能够处理的。 根据乘法原理,对于某种生成树的形态,其贡献为**每条边重的次数的乘积**。 如果把重边次数理解成权值的话,那么矩阵树定理求的就是 : 所有生成树边权乘积的总和。 (这里注意度数矩阵变成了相邻边的权值和) **例题** : [P3317 [SDOI2014]重建](https://www.luogu.com.cn/problem/P3317) - ## 有向扩展 前面都是无向图,神奇的是有向图的情况也是可以做的。 (邻接矩阵 $A$ 的意义同有向图邻接矩阵) 那么现在的矩阵 $D$ 就要变一下了。 若 $D[i][i]=\sum\limits_{j=1}^nA[j][i]$ ,即**到该点的边权总和(入)**。 此时求的就是**外向树** (从根向外) 若 $D[i][i]=\sum\limits_{j=1}^nA[i][j]$ ,即从**从该点出发的边权总和(出)**。 此时求的就是**内向树** (从外向根) (如果考场上不小心忘掉了,可以手玩小样例) (同样可以加权!) 此外,既然是有向的,那么就需要**指定根**。 前面提过要任意去掉第 $k$ 行与第 $k$ 列,是因为无向图所以不用在意谁为根。 在有向树的时候需要理解为指定根,结论是 : 去掉哪一行就是那一个元素为根。 **例题** : [P4455 [CQOI2018]社交网络](https://www.luogu.com.cn/problem/P4455) (内向树) 本题就是外向树,下面给出代码(出乎意料,跑的还挺快)。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define mod 1000000007 #define Maxn 305 using namespace std; ll powM(ll a,int t=mod-2) { ll ans=1; while(t){ if (t&1)ans=ans*a%mod; a=a*a%mod;t>>=1; }return ans; } int n,m; ll *a[Maxn],_a[Maxn][Maxn]; ll det(ll **a) { ll ans=1;bool tr=0; for (int j=1;j<n;j++){ for (int i=j;i<n;i++) if (a[i][j]){ if (i!=j){ swap(a[i],a[j]); tr=!tr; }break; } if (a[j][j]==0)return 0; ans=ans*a[j][j]%mod; ll t=powM(a[j][j]); for (int k=j;k<n;k++)a[j][k]=t*a[j][k]%mod; for (int i=j+1;i<n;i++){ t=mod-a[i][j]; for (int k=j;k<n;k++) a[i][k]=(a[i][k]+t*a[j][k])%mod; } }return tr? (mod-ans)%mod : ans; } int op; int main() { scanf("%d%d%d",&n,&m,&op); for (int i=1;i<=n;i++)a[i]=_a[i]; for (int i=1,f,t,w;i<=m;i++){ scanf("%d%d%d",&f,&t,&w); if (f==n)f=1;else if (f==1)f=n; if (t==n)t=1;else if (t==1)t=n; if (op==1){ a[f][t]=(a[f][t]-w+mod)%mod; a[t][t]=(a[t][t]+w)%mod; }else { a[f][t]=(a[f][t]-w+mod)%mod; a[t][t]=(a[t][t]+w)%mod; a[t][f]=(a[t][f]-w+mod)%mod; a[f][f]=(a[f][f]+w)%mod; } }printf("%lld",det(a)); return 0; } ```