bzoj4031 [HEOI2015]小Z的房间——矩阵树定理

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4031

矩阵树定理的模板题(第一次的矩阵树定理~)；

有点细节，放在注释里了。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int const mod=1e9;

int n,m,a[][],d[][],sid[][],tot,num[][];

ll ans=;

void add(int x,int y)

{

    d[x][x]++; d[y][y]++;

    sid[x][y]=; sid[y][x]=;

}

void gauss()

{

    int fl=;

    for(int i=;i<=tot;i++)

    {

        int nw=i;//

        for(int j=i+;j<=tot;j++)

            if(a[j][i]>a[nw][i])nw=j;

        if(nw!=i)

        {

            fl^=;

            for(int j=i;j<=tot;j++)swap(a[i][j],a[nw][j]);

        }

        for(int j=i+;j<=tot;j++)//上三角而非对角线

            while(a[j][i])

            {

                ll tmp=a[i][i]/a[j][i];

                for(int k=i;k<=tot;k++)

                {

                    ll tp=a[i][k]; a[i][k]=a[j][k];

                    a[j][k]=((tp-a[j][k]*tmp)%mod+mod)%mod;

                }

                fl^=;

            }

        (ans*=a[i][i])%=mod;

    }

    if(fl)ans=-ans;

    ans=((ans%mod)+mod)%mod;

}

int main()

{

    scanf("%d%d",&n,&m);

    char ch[][];

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

    {

        int nw=i%,pr=!nw;

        scanf("%s",ch[nw]+);

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

        {

            if(ch[nw][j]=='*')continue;//!!!

            tot++; num[nw][j]=tot;

            if(ch[nw][j-]=='.')add(tot,num[nw][j-]);

            if(ch[pr][j]=='.')add(tot,num[pr][j]);

        }

    }

    for(int i=;i<=tot;i++)

        for(int j=;j<=tot;j++)

            a[i][j]=(d[i][j]-sid[i][j]+mod)%mod;

    tot--;//

    gauss();

    printf("%lld",ans);

    return ;

}