LG4111/LOJ2122 「HEOI2015」小Z的房间 矩阵树定理

问题描述

LG4111

---

题解

矩阵树定理板子题。

---

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){

		fh=-1;ch=getchar();

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

int tot;

void fr(int &x){

	char ch=1;

	while(ch!='.'&&ch!='*') ch=getchar();

	if(ch=='.') x=++tot;

	else x=0;

}

int n,m;

int a[12][12],f[107][107];

int ans;

const int mod=1000000000;

void add(int x,int y){

	if(x>y) return;

	f[x][x]++,f[y][y]++;

	f[x][y]--,f[y][x]--;

}

void guass(){

	ans=1;

	for(int i=1;i<tot;i++){

		for(int j=i+1;j<tot;j++){

			while(f[j][i]){

				int t=f[i][i]/f[j][i];

				for(int k=i;k<tot;k++)

					f[i][k]=(f[i][k]-t*f[j][k]+mod)%mod;

				swap(f[i],f[j]);

				ans=-ans;

			}

		}

		ans=ans*f[i][i]%mod;

	}

	ans=(ans+mod)%mod;

}

signed main(){

	read(n);read(m);

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			fr(a[i][j]);

		}

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			int x=a[i][j],y;

			if(!x) continue;

			if(y=a[i][j-1]) add(x,y);

			if(y=a[i][j+1]) add(x,y);

			if(y=a[i-1][j]) add(x,y);

			if(y=a[i+1][j]) add(x,y);

		}

	}

//	for(int i=1;i<=tot;i++){

//		for(int j=1;j<=tot;j++){

//			cout<<f[i][j]<<" ";

//		}

//		cout<<endl;

//	}

	guass();

	printf("%lld\n",ans);

	return 0;

}