HEOI2015 小Z的房间

wjh15101051's space

卧薪尝胆，厚积薄发。

HEOI2015 小Z的房间

Date: Sun Jul 01 18:26:57 CST 2018

In Category: NoCategory

Description：

给你一个网格图，网格图中有一些格不能走，问打通一些格子间的墙得到一棵树的方案数。

模 $10^9$

$1 \le N \le 9$

Solution：

生成树个数用矩阵树定理，对于非质数模数无逆元不好高斯消元，但是发现方程之间两两可以相减，用类似欧几里得算法的方法将两个方程辗转相减，直到有一个方程变为零。注意交换两行时行列式变号，记一个 $tag$ 表示是否取负。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10

#define MOD 1000000000

typedef long long ll;

char p[MAXN][MAXN];

char getc()

{

    char c = getchar();

    while(c != '.' && c != '*')c = getchar();

    return c;

}

map<pair<int,int>,int> to;

ll g[MAXN * MAXN][MAXN * MAXN];

int mx[5] = {0,0,0,-1,1};

int my[5] = {0,1,-1,0,0};

int cnt = 0;

int main()

{

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

    memset(p,0,sizeof(p));

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

    {

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

        {

            p[i][j] = getc();

            if(p[i][j] == '.')to[make_pair(i,j)] = ++cnt;	

        }

    }

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

    {

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

        {

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

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

            {

                if(p[i + mx[k]][j + my[k]] == '.')

                {

                    ++g[to[make_pair(i,j)]][to[make_pair(i,j)]];

                    --g[to[make_pair(i,j)]][to[make_pair(i + mx[k],j + my[k])]];

                }

            }

        }

    }

    n = cnt;

    ll res = 1,tag = 1;

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

    {

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

        {

            g[i][j] = (g[i][j] % MOD + MOD) % MOD;

        }

    }

    --n;

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

    {

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

        {

            ll a = g[i][i],b = g[j][i];

            while(b)

            {

                ll div = a / b;

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

                {

                    g[i][k] = (g[i][k] - g[j][k] * div % MOD + MOD) % MOD;

                }

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

                {

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

                }

                a = a % b;swap(a,b);tag = -tag;

            }

        }

        res = res * g[i][i] % MOD;

    }

    if(tag == -1)res = (MOD - res) % MOD; 

    cout << res << endl;

    return 0;	

}

In tag: 数学-矩阵树定理

wjh15101051