发现身边的神仙们都会矩阵树定理，我这个菜鸡还不会，就来学了一下（
声明：本文 几乎 没有什么证明，感兴趣的读者可以看 这里。
行列式
定义
对于一个矩阵 (A_{i,j})，它的行列式 (det(A)=sumlimits_{P}(-1)^{ au(P)}prodlimits_{i=1}^nA_{i,P_i})。
其中 (P) 为 (1sim n) 的一个排列，( au(P)) 为 (P) 的逆序对数。
性质
- 上三角矩阵与下三角矩阵的行列式为对角线的乘积；
- 交换矩阵两行，矩阵行列式的值变号；
- 将矩阵的某一行乘 (k)，则矩阵行列式的值也乘 (k)；
- 矩阵中如果有两行（列）的值相同，则矩阵行列式的值为 (0)；
- 将矩阵某一行（列）加上另一行（列）的 (k) 倍，行列式的值不变。
代码
使用消元法求解。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define DC int T = gi <int> (); while (T--)
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
template <typename T>
inline T gi()
{
T f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int INF = 0x3f3f3f3f, N = 603, M = N << 1;
int n, mod;
LL a[N][N];
inline LL solve()
{
LL ans = 1, op = 1;
for (int i = 1; i <= n; i+=1)
{
for (int j = i + 1; j <= n; j+=1)
{
while (a[i][i])
{
int p = a[j][i] / a[i][i];
for (int k = i; k <= n; k+=1)
{
a[j][k] = ((a[j][k] - 1ll * p * a[i][k]) % mod + mod) % mod;
swap(a[i][k], a[j][k]);
}
op *= -1;
}
swap(a[i], a[j]);
op *= -1;
}
ans = ans * a[i][i] % mod;
}
return (ans * op % mod + mod) % mod;
}
int main()
{
n = gi <int> (), mod = gi <int> ();
for (int i = 1; i <= n; i+=1) for (int j = 1; j <= n; j+=1) a[i][j] = gi <LL> ();
printf("%lld
", solve());
return 0;
}
无向图
设一张图 (G) 的度数矩阵为 (D)，邻接矩阵为 (A)。
易得：
[D_{i,j}=
egin{cases}
deg(i)&{i=j}\
0&{i
ot =j}
end{cases}
]
则图的基尔霍夫（Kirchhoff）矩阵 (L=D-A)。
设 (L') 为基尔霍夫矩阵 (L) 去掉第 (i) 行和第 (i) 列（其中 (1le ile n)）得到的新矩阵，则 (det(L')) 即为图 (G) 的生成树个数（(det(L')) 为矩阵 (L') 的行列式）。
有向图
修改一下度数矩阵 (D) 的定义：
- 若题目要求的是外向树个数，则 (D) 为入度矩阵，即：
[D_{i,j}=
egin{cases}
deg_{in}(i)&{i=j}\
0&{i
ot =j}
end{cases}
]
- 若题目要求的是内向树个数，则 (D) 为出度矩阵，即：
[D_{i,j}=
egin{cases}
deg_{out}(i)&{i=j}\
0&{i
ot =j}
end{cases}
]
注意这里依然要去掉一行一列，只是这里去掉的第 (i) 行第 (i) 列就代表生成树的根为 (i)。
代码
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define DC int T = gi <int> (); while (T--)
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
template <typename T>
inline T gi()
{
T f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int INF = 0x3f3f3f3f, N = 303, M = N << 1, mod = 1000000007;
int n, m, t;
LL d[N][N], a[N][N], l[N][N];
inline LL solve()
{
LL ans = 1, op = 1;
for (int i = 2; i <= n; i+=1)
{
for (int j = i + 1; j <= n; j+=1)
{
while (l[i][i])
{
int p = l[j][i] / l[i][i];
for (int k = i; k <= n; k+=1)
{
l[j][k] = ((l[j][k] - 1ll * p * l[i][k] % mod) % mod + mod) % mod;
swap(l[i][k], l[j][k]);
}
op *= -1;
}
swap(l[i], l[j]);
op *= -1;
}
ans = ans * l[i][i] % mod;
}
return (ans * op % mod + mod) % mod;
}
int main()
{
//File("");
n = gi <int> (), m = gi <int> (), t = gi <int> ();
for (int i = 1; i <= m; i+=1)
{
int u = gi <int> (), v = gi <int> (), w = gi <int> ();
if (!t)
{
(d[u][u] += w) %= mod, (d[v][v] += w) %= mod;
(a[u][v] += w) %= mod, (a[v][u] += w) %= mod;
}
else
{
(d[v][v] += w) %= mod;
(a[u][v] += w) %= mod;
}
}
for (int i = 1; i <= n; i+=1)
for (int j = 1; j <= n; j+=1)
l[i][j] = d[i][j] - a[i][j];
printf("%lld
", solve());
return 0;
}
参考学习
https://www.cnblogs.com/zj75211/p/8039443.html
https://www.luogu.com.cn/blog/command-block/ju-zhen-shu-ding-li-xing-lie-shi-post