题意：求某网格图生成树个数，对1e9取模

题解：题目是裸的Matrix-Tree定理，这不是我要说的重点，重点是对于这个取模的处理。

由于这不是个质数，所以不能直接乘逆元来当除法用。直接高斯消元肯定是不行的，须要一定实现的小技巧。

我们能够考虑gcd的实现过程，辗转相除直到一个为0。多么好的思路，对于这个问题我们也能够这样处理。每次减掉对应的倍数就可以

以下是代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef double db;

const int inf=0x3f3f3f3f;

int getint()

{

    int f=1,g=0;char c=getchar();

    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0' && c<='9')g=(g<<3)+(g<<1)+c-'0',c=getchar();

    return f*g;

}

const int maxn=105;

const int maxl=10;

const int mod=1000000000;

const int dx[]={0,0,-1,1};

const int dy[]={1,-1,0,0};

char c[maxl][maxl];

ll a[maxn][maxn];

int pos[maxn][maxn];

int tot;

ll det(int n)

{

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

    {

        for(int j=1;j<=n;j++)

        {

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

        }

    }

    ll f=1,res=1ll;

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

    {

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

        {

            int a1=a[i][i];

            int b1=a[j][i];

            while(b1!=0)

            {

                ll temp=a1/b1;

                a1%=b1;swap(a1,b1);

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

                {

                    a[i][k]=(a[i][k]-temp*a[j][k]%mod+mod)%mod;

                }

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

                {

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

                }

                f=-f;

            }

        }

        if(!a[i][i])return 0;

        res=res*a[i][i]%mod;

    }

    res*=f;

    res=(res+mod)%mod;

    return res;

}

int main()

{

//  freopen("in.txt","r",stdin);

    int n=getint();

    int m=getint();

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

    {

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

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

        {

            if(c[i][j]!='*')pos[i][j]=++tot;

        }

    }

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

    {

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

        {

            if(!pos[i][j])continue;

            for(int k=0;k<4;k++)

            {

                int tx=i+dx[k];

                int ty=j+dy[k];

                if(ty<1 || tx<1 || tx>n || ty>m || !pos[tx][ty])continue;

                a[pos[i][j]][pos[i][j]]++;

                a[pos[i][j]][pos[tx][ty]]--;

            }

        }

    }

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

    return 0;

}