BZOJ 4031: [HEOI2015]小Z的房间 Matrix-Tree定理

题目链接：

http://www.lydsy.com/JudgeOnline/problem.php?id=4031

题解：

Matrix-tree定理解决生成树计数问题，其中用到高斯消元法求上三角矩阵，其中消元用的是辗转相除法。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod = 1e9;

const int maxn = ;

typedef long long LL;

int n, m, tot;

char str[maxn][maxn];

int mp[maxn][maxn];

LL C[maxn][maxn];

const int dx[] = { ,,-, };

const int dy[] = { -,,, };

LL Det(int n) {

    LL ret = ;

    int f = ;

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

        for (int j = ; j <= n; j++) {

            C[i][j] = (C[i][j] % mod + mod) % mod;

        }

    }

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

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

            int A = C[i][i], B = C[j][i];

            while (B!=) {

                LL t = A / B; A = A%B; swap(A, B);

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

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

                }

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

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

                }

                f = -f;

            }

        }

        ret = ret*C[i][i] % mod;

    }

    if (f == -) ret = ((-ret)%mod + mod) % mod;

    return ret;

}

void init() {

    tot = ;

    memset(C, , sizeof(C));

}

int main() {

    while (scanf("%d%d", &n, &m) ==  && n) {

        init();

        for (int i = ; i < n; i++) scanf("%s", str[i]);

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

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

                if (str[i][j] == '.') {

                    mp[i][j] = ++tot;

                }

            }

        }

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

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

                if (str[i][j] == '.') {

                    for (int t = ; t < ; t++) {

                        int ii = i + dx[t], jj = j + dy[t];

                        if (ii <  || ii >= n || jj <  || jj >= m || str[ii][jj] == '*') continue;

                        C[mp[i][j]][mp[i][j]]++;

                        C[mp[i][j]][mp[ii][jj]]--;

                    }

                }

            }

        }

        LL ans=Det(tot - );

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

    }

    return ;

}