【LOJ】#2122. 「HEOI2015」小 Z 的房间

题解

又是一道取模不给质数的毒瘤矩阵树题

不会写分数类……然后发现了网上过于神仙的题解类似与辗转相除的这样把某一个位置消成0 orz

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define enter putchar('
')
#define space putchar(' ')
#define MAXN 150005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef long double db;
typedef unsigned int u32;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {putchar('-');x = -x;}
    if(x >= 10) out(x / 10);
    putchar('0' + x % 10);
}
const int MOD = 1000000000;
int N,M;
char s[15][15];
int id[15][15],cnt;
int dx[] = {0,-1,0,1},dy[] = {1,0,-1,0};

int64 g[105][105];
int64 Guass() {
    int64 res = 1;--cnt;
    for(int i = 1 ; i <= cnt ; ++i) {
	for(int j = i + 1 ; j <= cnt ; ++j) {
	    while(g[j][i]) {
		int64 t = g[i][i] ? g[j][i] / g[i][i] : 0;
		for(int h = i ; h <= cnt ; ++h) {
		    g[j][h] = ((g[j][h] - t * g[i][h]) % MOD + MOD) % MOD;
		    swap(g[j][h],g[i][h]);
		}
		res = -res;
	    }
	}
    }
    for(int i = 1 ; i <= cnt ; ++i) {
	res = res * g[i][i] % MOD;
    }
    return (res + MOD) % MOD;
}
void Solve() {
    read(N);read(M);
    for(int i = 1 ; i <= N ; ++i) {
	scanf("%s",s[i] + 1);
	for(int j = 1 ; j <= M ; ++j) {
	    if(s[i][j] == '.') id[i][j] = ++cnt;
	}
    }
    for(int i = 1 ; i <= N ; ++i) {
	for(int j = 1 ; j <= M ; ++j) {
	    if(!id[i][j]) continue; 
	    for(int k = 0 ; k <= 3 ; ++k) {
		int x = i + dx[k],y = j + dy[k];
		if(id[x][y]) {
		    g[id[i][j]][id[x][y]] -= 1;
		    g[id[i][j]][id[i][j]] += 1;
		}
	    }
	}
    }
    for(int i = 1 ; i <= cnt ; ++i) {
	for(int j = 1 ; j <= cnt ; ++j) {
	    g[i][j] = (g[i][j] + MOD) % MOD;
	}
    }
    out(Guass());enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}