题目链接

BZOJ4031

题解

第一眼：这不裸的矩阵树定理么

第二眼：这个模\(10^9\)是什么鬼嘛QAQ

想尝试递归求行列式，发现这是\(O(n!)\)的。。

想上高斯消元，却又处理不了逆元这个东西、、

无奈去翻题解，，，

发现可以用类似辗转相除法去消，而避免除法，，，

这样子依旧是每次一行减去另一行乘一个数，行列式不变

orz

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 105,maxm = 100005,INF = 1000000000,P = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int visx[maxn],A[maxn][maxn],n,m,N,id[maxn][maxn];

int X[4] = {0,0,1,-1},Y[4] = {-1,1,0,0};

char s[maxn][maxn];

int Gause(){

	int tag = 1;

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

		int j = i;

		for (int k = i + 1; k < N; k++)

			if (abs(A[k][i]) > abs(A[j][i])) j = k;

		if (j != i){

			for (int k = i; k < N; k++) swap(A[i][k],A[j][k]);

			tag = -tag;

		}

		for (j = i + 1; j < N; j++){

			while (A[j][i]){

				int tmp = A[j][i] / A[i][i];

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

					A[j][k] = ((A[j][k] - 1ll * tmp * A[i][k] % P) % P + P) % P;

				if (A[j][i]){

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

						swap(A[i][k],A[j][k]);

					tag = -tag;

				}

			}

		}

	}

	int re = 1;

	for (int i = 1; i < N; i++)

		re = 1ll * re * A[i][i] % P;

	return (re * tag % P + P) % P;

}

int main(){

	n = read(); m = read();

	REP(i,n){

		scanf("%s",s[i] + 1);

		REP(j,m) if (s[i][j] == '.') id[i][j] = ++N;

	}

	REP(i,n) REP(j,m){

		if (s[i][j] == '*') continue;

		int nx,ny,u = id[i][j];

		for (int k = 0; k < 4; k++){

			nx = i + X[k];

			ny = j + Y[k];

			if (nx < 1 || ny < 1 || nx > n || ny > m || s[nx][ny] == '*') continue;

			A[u][u]++;

			A[u][id[nx][ny]] = -1;

		}

	}

	printf("%d\n",Gause());

	return 0;

}