LG4111/LOJ2122 「HEOI2015」小Z的房间 矩阵树定理

问题描述

LG4111

题解

矩阵树定理板子题。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

int tot;

void fr(int &x){
    char ch=1;
    while(ch!='.'&&ch!='*') ch=getchar();
    if(ch=='.') x=++tot;
    else x=0;
}

int n,m;
int a[12][12],f[107][107];

int ans;

const int mod=1000000000;

void add(int x,int y){
    if(x>y) return; 
    f[x][x]++,f[y][y]++;
    f[x][y]--,f[y][x]--;
}

void guass(){
    ans=1;
    for(int i=1;i<tot;i++){
        for(int j=i+1;j<tot;j++){
            while(f[j][i]){
                int t=f[i][i]/f[j][i];
                for(int k=i;k<tot;k++)
                    f[i][k]=(f[i][k]-t*f[j][k]+mod)%mod;
                swap(f[i],f[j]);
                ans=-ans;
            }
        }
        ans=ans*f[i][i]%mod;
    }
    ans=(ans+mod)%mod;
}

signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fr(a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=a[i][j],y;
            if(!x) continue;
            if(y=a[i][j-1]) add(x,y);
            if(y=a[i][j+1]) add(x,y);
            if(y=a[i-1][j]) add(x,y);
            if(y=a[i+1][j]) add(x,y);
        }
    }
//  for(int i=1;i<=tot;i++){
//      for(int j=1;j<=tot;j++){
//          cout<<f[i][j]<<" ";
//      }
//      cout<<endl;
//  }
    guass();
    printf("%lld\n",ans);
    return 0;
}