bzoj 4031: 小Z的房间 矩阵树定理

bzoj 4031: 小Z的房间 矩阵树定理

题目:

题解:

矩阵树板子题.

刚学的矩阵树定理,练练手.

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;static char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=(x<<1)+(x<<3)+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

#define rg register int

#define rep(i,a,b) for(rg i=(a);i<=(b);++i)

#define per(i,a,b) for(rg i=(a);i>=(b);--i)

const int maxn = 128;

const int mod = 1e9;

char s[maxn][maxn];

int id[maxn][maxn],nodecnt;

int a[maxn][maxn];

inline int det(int n){

    int ret = 1,s=0;

    rep(i,1,n){

        rg r = i;

        for(r=i;r <= n;++r) if(a[r][i] != 0) break;

            if(r == n+1) return 0;

        if(r != i){

            s ^= 1;

            rep(j,i,n) swap(a[r][j],a[i][j]);

        }

        rep(j,i+1,n){

            while(a[j][i]){

                int x = a[j][i]/a[i][i];

                rep(k,i,n){

                    a[j][k] -= 1LL*a[i][k]*x % mod;

                    if(a[j][k] < 0) a[j][k] += mod;

                }

                if(a[j][i] == 0) break;

                s ^= 1;

                rep(k,i,n) swap(a[j][k],a[i][k]);

            }

        }

        ret = 1LL*ret*a[i][i] % mod;

    }

    if(s) ret = mod - ret;

    return ret;

}

int main(){

    int n,m;read(n);read(m);

    rg u,v;

    rep(i,1,n){

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

        rep(j,1,m){

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

            id[i][j] = ++ nodecnt;

            u = id[i][j];

                if(s[i-1][j] == '.'){

                v = id[i-1][j];

                ++ a[u][u]; ++ a[v][v];

                -- a[u][v]; -- a[v][u];

            }

            if(s[i][j-1] == '.'){

                v = id[i][j-1];

                ++ a[u][u]; ++ a[v][v];

                -- a[u][v]; -- a[v][u];

            }

        }

    }

    int lim = nodecnt;

    rep(i,1,n*m) rep(j,1,lim){

        if(a[i][j] >= mod) a[i][j] -= mod;

        if(a[i][j] < 0) a[i][j] += mod;

    }

    printf("%d\n",det(lim-1));

    return 0;

}