请注意，此文章内不含任何证明，因为我懒的写也不会，就先记着个结论好了

比较详细但易懂的证明可见这里

Matrix-Tree

Brief Introduction

用来求解无向图生成树个数的结论

设GG表示邻接矩阵，DD表示度数矩阵。定义基尔霍夫矩阵C=D−GC=D-G

将基尔霍夫任意去掉对角线上的任意一个位置所在行和所在列，形成一个行列式，高斯消元求出行列式的值即为答案。

有向图

有向图的生成树也可以用Matrix−TreeMatrix-Tree定理计算。

外向树就是入度矩阵-邻接矩阵；内向树就是出度矩阵-邻接矩阵。

求解行列式

注：这里也只有结论

行列式的值

det(A)=∑(p1p2...pn)δ(p1p2...pn)a1,p1a2,p2...an,pn=∣A∣ det(A)=\sum\limits_{(p_1p_2...p_n)}\delta(p_1p_2...p_n)a_{1,p_1}a_{2,p_2}...a_{n,p_n}=|A|

其中δ(i1i2...in)=(−1)t\delta(i_1i_2...i_n)=(-1)^{t}，tt是逆序对的个数，可以将排列分为奇排列和偶排列

本来还写了一些鬼畜的理解方法，看了一点线代之后发现这个还是挺好理解的

上面那个式子已经写的很清楚了

实在要解释一下的话，那个∑\sum就是在枚举所有排列，然后对每个排列都求出其中元素的乘积，乘上−1-1的逆序对数次方，最后把所有排列的答案求和

几个重要性质

  • 交换矩阵的任意两行或任意两列，行列式的值取相反数。
  • 矩阵的一行减去另一行的 kk 倍，行列式不变。

有了这两个性质就能用高斯消元求解了，把矩阵消乘对角矩阵，对角线值的乘积即为答案

Code（模意义下）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
namespace Matrix
{
	const int maxn = 300 + 10;

	int A[maxn][maxn];

	inline void init () { memset(A, 0, sizeof A); }

	inline void add_edge (int x, int y) { ++A[x][x], ++A[y][y], --A[x][y], --A[y][x]; }

	inline int gauss (int n)
	{
		int ans = 1;
		for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) A[i][j] = (A[i][j] + Mod) % Mod;

		for (int i = 1; i <= n; ++i)
		{
			if (!A[i][i])
			{
				int id = i;
				for (int j = i + 1; j <= n; ++j)
					if (A[j][i])
					{
						swap(A[i], A[j]);
						ans = (LL)ans * (Mod - 1) % Mod;
						break;
					}
				if (!ans) return 0;
			}

			int inv = Pow(A[i][i], Mod - 2);
			for (int j = i + 1; j <= n; ++j)
			{
				int now = (LL)A[j][i] * inv % Mod;
				for (int k = i + 1; k <= n; ++k) Add (A[j][k], Mod - (LL)now * A[i][k] % Mod);
				A[j][i] = 0;
			}
		}

		for (int i = 1; i <= n; ++i) ans = (LL)ans * A[i][i] % Mod;

		return ans;
	}
}