题意
给定一个 $n\times m$ 的矩阵, 一些格子是障碍, 相邻的格子(四联通)之间可以连边, 求把非障碍的格子连成一棵树的方案数量 $\bmod 10^9$ 的值.
$n,m\le 9$.
题解
一些奇怪的东西
做题过程:
- 这个数据范围怎么这么像大力状压啊
- 怎么还要联通性啊不会是插头DP吧
- woc连成树? 矩阵树定理sb题?
- 码码码…
- 哦淦这个模数怎么没逆元啊QAQ
正经内容
其实就是个矩阵树定理sb题…
矩阵树定理内容:
一个 $n$ 个点的图的生成树个数即为其 Laplacian 矩阵的任一 $n-1$ 阶余子式的行列式的值.
构造出Laplacian矩阵, 丢掉一行一列然后高斯消元消成上三角, 最后把对角线上的元素乘起来就是答案了.
但是这题高消的时候遇到了一些问题: 没有逆元.
这就比较辣手了qwq…
但是我们可以用另一个高端操作来消元: 辗转相除.
辗转相除求 $\gcd$ 的时候最后一定能把其中一个值消成 $0$, 此时另一个值就是 $\gcd$. 但是这里我们关注点不是 $\gcd$ 而是如何把其中一个值消成 $0$.
但是初等行变换可没有整行取模这种操作.
考虑取模本质上是什么. 我们不难得到下面这个显然的式子:
$$
a\bmod b=a-\left \lfloor \frac a b \right \rfloor b
$$
这样我们就可以用 $\left \lfloor \frac a p \right \rfloor$ 做系数来初等行变换消元了. 消一个 $n$ 阶矩阵的时间复杂度是 $O(n^3\log p)$ 的.
总时间复杂度 $O\big((nm)^3\log p\big)$.
参考代码
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
|
#include <bits/stdc++.h>
const int MOD=1e9;
const int MAXN=110;
typedef long long intEx;
const int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n;
int m;
int cnt;
int id[MAXN][MAXN];
std::vector<intEx> mt[MAXN];
int GaussDet(int);
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;
scanf(" %c",&ch);
if(ch=='.')
id[i][j]=++cnt;
}
}
for(int i=1;i<=cnt;i++)
mt[i].resize(cnt+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(id[i][j]){
for(int k=0;k<4;k++){
if(id[i+d[k][0]][j+d[k][1]]){
--mt[id[i+d[k][0]][j+d[k][1]]][id[i][j]];
++mt[id[i][j]][id[i][j]];
}
}
}
}
}
printf("%d\n",GaussDet(cnt));
return 0;
}
int GaussDet(int n){
intEx ans=1;
for(int i=1;i<n;i++){
for(int j=i+1;j<n;j++){
while(mt[j][i]!=0){
intEx r=mt[i][i]/mt[j][i];
for(int k=i;k<n;k++)
(mt[i][k]-=r*mt[j][k])%=MOD;
std::swap(mt[i],mt[j]);
ans=-ans;
}
}
(ans*=mt[i][i])%=MOD;
}
return (ans%MOD+MOD)%MOD;
}
|
