[HAOI2015]小Z的房间

Posted on | In

最近多校联考天天爆零搞得心态有点炸

某天联考有道矩阵树定理，然而我不会

所以就被一堆神仙爆踩了

后来觉得还是得补一补矩阵树定理，也算是涨个姿势

但是行列式真的好难啊

这题就是矩阵树定理模板题

首先把原图转换成基尔霍夫矩阵

对于每个点特判它上方的点和左边的点

如果是房间就可以连，如果是柱子就不能连

因为模数不是质数，所以高斯消元要用辗转相除法

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
#include<bits/stdc++.h>
#define mod 1000000000
using namespace std;
char s[11][11];
int a[101][101],id[101][101];
int main () {
	register int m,n,num=0; scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i) scanf("%s",s[i]+1);
	for(register int i=1;i<=n;++i)
	    for(register int j=1;j<=m;++j)
	        if(s[i][j]=='.') id[i][j]=++num;
	for(register int i=1;i<=n;++i)
	    for(register int j=1;j<=m;++j)
	        if(s[i][j]=='.') {
	        	if(s[i-1][j]=='.') {
	        		++a[id[i-1][j]][id[i-1][j]];
					++a[id[i][j]][id[i][j]];
	        		--a[id[i-1][j]][id[i][j]];
					--a[id[i][j]][id[i-1][j]];
				}
	        	if(s[i][j-1]=='.') {
	        		++a[id[i][j-1]][id[i][j-1]];
					++a[id[i][j]][id[i][j]];
	        		--a[id[i][j-1]][id[i][j]];
					--a[id[i][j]][id[i][j-1]];
				}
			}
	register long long ans=1;
	for(register int i=1;i<num;++i) {
		for(register int j=i+1;j<num;++j)
	        while(a[j][i]) {
	        	register int x=a[i][i]/a[j][i];
	        	for(register int k=i;k<num;++k) {
	        		register long long tmp=(long long)a[j][k]*x%mod;
	        		a[i][k]=((long long)a[i][k]-tmp+mod)%mod;
				}
				swap(a[i],a[j]),ans=-ans;
			}
		(ans*=a[i][i])%=mod,(ans+=mod)%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}