目录

[BZOJ 4031][LOJ 2122][HEOI 2015] 小Z的房间

迁移提示
本文迁移自博客园, 原文链接

[BZOJ 4031][LOJ 2122][HEOI 2015] 小Z的房间

题意

给定一个 $n\times m$ 的矩阵, 一些格子是障碍, 相邻的格子(四联通)之间可以连边, 求把非障碍的格子连成一棵树的方案数量 $\bmod 10^9$ 的值.

$n,m\le 9$.

题解

一些奇怪的东西

做题过程:

  1. 这个数据范围怎么这么像大力状压啊
  2. 怎么还要联通性啊不会是插头DP吧
  3. woc连成树? 矩阵树定理sb题?
  4. 码码码…
  5. 哦淦这个模数怎么没逆元啊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;
}

https://pic.rvalue.moe/2021/08/02/25fdf4c102153.jpg