BZOJ 4031: [HEOI2015]小Z的房间 矩阵树定理

这里的模数不是质数，所以需要用类似辗转相除的方式进行高斯消元.   

code:

#include <cstdio> 
#include <algorithm>   
#define N 100   
#define ll long long 
#define mod 1000000000     
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
int n,m,cnt=0;     
char S[N][N];    
int a[N][N],id[N][N];           
void op(int x,int y) 
{
    if(y)
    {
        ++a[y][y];     
        --a[x][y];      
    }
}
int gauss() 
{
    int i,j,k,ans=1;    
    for(i=1;i<=cnt;++i) 
    {    
        for(j=i+1;j<=cnt;++j)    
        {
            while(a[j][i])    
            {
                int t=a[i][i]/a[j][i];       
                for(k=i;k<=cnt;++k)   a[i][k]=(ll)(a[i][k]%mod-(ll)t*a[j][k]%mod+mod)%mod;    
                swap(a[i],a[j]),ans*=-1;   
            }
        }
        if(!a[i][i]) return 0;  
    } 
    if(ans<0) ans+=mod;   
    for(i=1;i<=cnt;++i) ans=(ll)((ll)ans*a[i][i]%mod+mod)%mod;    
    return ans;       
}
int main() 
{ 
    // setIO("input"); 
    int i,j;   
    scanf("%d%d",&n,&m);       
    for(i=1;i<=n;++i) scanf("%s",S[i]+1);         
    for(i=1;i<=n;++i) for(j=1;j<=m;++j)  if(S[i][j]=='.') id[i][j]=++cnt;                   
    for(i=1;i<=n;++i) 
    {
        for(j=1;j<=m;++j)    
            if(id[i][j]) 
            {
                op(id[i][j],id[i-1][j]); 
                op(id[i][j],id[i+1][j]); 
                op(id[i][j],id[i][j-1]); 
                op(id[i][j],id[i][j+1]);     
            }
    }   
    --cnt;    
    printf("%d
",gauss());           
    return 0;
}