BZOJ 4031 小Z的房间

矩阵树定理第二题，用于有取模处理的运算。
中间一直超时，还一位bzoj会卡宏定义……真是石乐志

题意：
给你一个n×m矩阵，矩阵中的’ . ‘表示成一个房间，’ * ‘ 表示柱子，在相邻的房间中可以连边，要求每个房间都相连，求方案数。

思路：
算是比较裸的矩阵树定理应用了，对每一个点，标号，再对相邻都是点的格子建边。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

typedef long long ll;
const int maxn = 105;
const int mod = 1e9;

ll c[maxn][maxn];
char mat[maxn][maxn];
int G[maxn][maxn];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

ll getDet(ll a[][maxn], int n)
{
    range(i, 1, n) range(j, 1, n) a[i][j] = (a[i][j] + mod) % mod;
    ll ret = 1;
    range(i, 1, n - 1)
    {
        range(j, i + 1, n - 1) while (a[j][i])
        {
            ll t = a[i][i] / a[j][i];
            range(k, i, n - 1) a[i][k] = (a[i][k] - a[j][k] * t % mod + mod) % mod;
            range(k, i, n - 1) swap(a[i][k], a[j][k]);
            ret = -ret;
        }
        if (a[i][i] == 0)
            return 0;
        ret = ret * a[i][i] % mod;
    }
    return (ret + mod) % mod;
}

int main()
{
    int n, m, num = 0;
    scanf("%d %d", &n, &m);
    each(i, n) scanf("%s", mat[i]);
    each(i, n) each(j, m) if (mat[i][j] == '.') G[i][j] = ++num;
    each(i, n) each(j, m) if (G[i][j])
    {
        int u = G[i][j];
        each(k, 4)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x < 0 || x >= n || y < 0 || y >= m || mat[x][y] != '.')
                continue;
            int v = G[x][y];
            c[u][u]++, c[u][v]--;
        }
    }
    printf("%lld\n", getDet(c, num));
    return 0;
}