高斯消元
模板 luogu P3389
1 |
|
ICPC2020 Jinan
1 |
|
\(mod 2\)等价于异或，所以可以用bitset优化一个64的常数。
矩阵树定理
本章节的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，转自OIWIKI Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。
本篇记号声明
本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。
无向图情况
设 \(G\) 是一个有 \(n\) 个顶点的无向图。定义度数矩阵 \(D(G)\) 为：
\[ D_{ii}(G) = \mathrm{deg}(i), D_{ij} = 0, i\neq j \]
设 \(\#e(i,j)\) 为点 \(i\) 与点 \(j\) 相连的边数，并定义邻接矩阵 \(A\) 为：
\[ A_{ij}(G)=A_{ji}(G)=\#e(i,j), i\neq j \]
定义 Laplace 矩阵（亦称 Kirchhoff 矩阵）\(L\) 为：
\[ L(G) = D(G) - A(G) \]
记图 \(G\) 的所有生成树个数为 \(t(G)\)。
有向图情况
设 \(G\) 是一个有 \(n\) 个顶点的有向图。定义出度矩阵 \(D^{out}(G)\) 为：
\[ D^{out}_{ii}(G) = \mathrm{deg^{out}}(i), D^{out}_{ij} = 0, i\neq j \]
类似地定义入度矩阵 \(D^{in}(G)\)
设 \(\#e(i,j)\) 为点 \(i\) 指向点 \(j\) 的有向边数，并定义邻接矩阵 \(A\) 为：
\[ A_{ij}(G)=\#e(i,j), i\neq j \]
定义出度 Laplace 矩阵 \(L^{out}\) 为：
\[ L^{out}(G) = D^{out}(G) - A(G) \]
定义入度 Laplace 矩阵 \(L^{in}\) 为：
\[ L^{in}(G) = D^{in}(G) - A(G) \]
记图 \(G\) 的以 \(r\) 为根的所有根向树形图个数为 \(t^{root}(G,r)\)。所谓根向树形图，是说这张图的基图是一棵树，所有的边全部指向父亲。
记图 \(G\) 的以 \(r\) 为根的所有叶向树形图个数为 \(t^{leaf}(G,r)\)。所谓叶向树形图，是说这张图的基图是一棵树，所有的边全部指向儿子。
定理叙述
矩阵树定理具有多种形式。其中用得较多的是定理 1、定理 3 与定理 4。
定理 1（矩阵树定理，无向图行列式形式） 对于任意的 \(i\)，都有
\[ t(G) = \det L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n} \]
其中记号 \(L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n}\) 表示矩阵 \(L(G)\) 的第 \(1,\cdots,i-1,i+1,\cdots,n\) 行与第 \(1,\cdots,i-1,i+1,\cdots,n\) 列构成的子矩阵(原矩阵去掉第\(i\)行同时去掉第\(i\)列（\(1\leq i\leq n\)），即矩阵的主子式)。也就是说，无向图的 Laplace 矩阵具有这样的性质，它的所有 \(n-1\) 阶主子式都相等。
定理 2（矩阵树定理，无向图特征值形式） 设 \(\lambda_1, \lambda_2, \cdots, \lambda_{n-1}\) 为 \(L(G)\) 的 \(n - 1\) 个非零特征值，那么有
\(t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\)
定理 3（矩阵树定理，有向图根向形式） 对于任意的 \(k\)，都有
\[ t^{root}(G,k) = \det L^{out}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} \]
因此如果要统计一张图所有的根向树形图，只要枚举所有的根 \(k\) 并对 \(t^{root}(G,k)\) 求和即可。
定理 4（矩阵树定理，有向图叶向形式） 对于任意的 \(k\)，都有
\[ t^{leaf}(G,k) = \det L^{in}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} \]
因此如果要统计一张图所有的叶向树形图，只要枚举所有的根 \(k\) 并对 \(t^{leaf}(G,k)\) 求和即可。 ### 「HEOI2015」小 Z 的房间 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using namespace std;
const int N=105;
char mp[N][N];
int n,m;
typedef long long ll;
ll L[N][N];
int id[N][N],cnt;
const ll mod=1e9;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",mp[i]+1);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(mp[i][j]=='.'){
id[i][j]=++cnt;
if(mp[i-1][j]=='.'){
L[id[i][j]][id[i-1][j]]--;
L[id[i-1][j]][id[i][j]]--;
L[id[i][j]][id[i][j]]++;
L[id[i-1][j]][id[i-1][j]]++;
}
if(mp[i][j-1]=='.'){
L[id[i][j]][id[i][j-1]]--;
L[id[i][j-1]][id[i][j]]--;
L[id[i][j]][id[i][j]]++;
L[id[i][j-1]][id[i][j-1]]++;
}
}
}
}
int r=cnt-1;
for(int i=1;i<=r;++i){
for(int j=1;j<=r;++j){
L[i][j]=(L[i][j]+mod)%mod;
}
}
ll ans=1;
for(int i=1;i<=r;++i){
for(int j=i+1;j<=r;++j){
while(L[j][i]){
ll t=L[i][i]/L[j][i];
for(int k=i;k<=r;++k){
L[i][k]=(L[i][k]-t*L[j][k]%mod+mod)%mod;
swap(L[i][k],L[j][k]);
}
ans*=-1;
}
}
ans=ans*L[i][i]%mod;
}
printf("%lld",(ans+mod)%mod);
return 0;
}
Luogu P2144 [FJOI2007]轮状病毒
需要高精度 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24n=int(input())
n=n+1
a=[[0 for i in range(n+2)]for j in range(n+2)]
a[1][1]=n-1
a[2][n]=-1
a[n][2]=-1
for i in range(2,n+1):
a[i][1]=-1
a[1][i]=-1
a[i][i]=3
if i+1<=n :
a[i][i+1]=-1
a[i+1][i]=-1
ans=1
for i in range(1,n):
for j in range(i+1,n):
while a[j][i]!=0:
t=a[i][i]//a[j][i]
for k in range(i,n):
a[i][k]-=t*a[j][k]
a[i][k],a[j][k]=a[j][k],a[i][k]
ans=-ans
ans*=a[i][i]
print(ans)