【bzoj5133】[CodePlus2017年12月]白金元首与独舞 并查集+矩阵树定理

时间：2023-12-13 11:38:08

题目描述

给定一个 $n\times m$ 的方格图，每个格子有 ↑、↓、←、→，表示从该格子能够走到相邻的哪个格子。
有一些格子是空着的，需要填上四者之一，需要满足：最终的方格图中，从任意一个位置出发都能够走出方格图。求方案数 mod 10^9+7。

$数据组数\le 10$ ，$n,m\le 300$ ，$空格子数k\le 200$

题解

并查集+矩阵树定理

由于k很小，又是计数问题，考虑矩阵树定理。

先使用并查集处理出从每个位置开始，最终会走到哪个位置。显然如果有环则答案为0，否则一定走到的是一个空格子或方格图外部。

这样就不用考虑已填好的格子的走法，只需要考虑空格子的走法即可。

每个空格子需要走到方格图外部，不能有环，相当于是一棵以方格图外部为根的内向树形图。

考虑每个空格子4个方向会走到哪个空格子（或外部），连边，矩阵树定理求解即可。

本题要求的是内向树，因此求 出度矩阵-邻接矩阵 删去根节点所在行列，得到的行列式的值 即可。

时间复杂度 $O(nm+k^3)$

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mod 1000000007

using namespace std;

typedef long long ll;

int id[210][210] , f[40010] , flag , v[40010] , wx[310] , wy[310];

ll a[310][310];

char str[210];

inline ll pow(ll x , int y)

{

    ll ans = 1;

    while(y)

    {

        if(y & 1) ans = ans * x % mod;

        x = x * x % mod , y >>= 1;

    }

    return ans;

}

int find(int x)

{

    return x == f[x] ? x : f[x] = find(f[x]);

}

inline void link(int x , int y)

{

    x = find(x) , y = find(y);

    if(x == y) flag = 1;

    f[x] = y;

}

int main()

{

    int T;

    scanf("%d" , &T);

    while(T -- )

    {

        int n , m , p = 0 , i , j , k , d = 0;

        ll t , ans = 1;

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

        memset(id , 0 , sizeof(id)) , flag = 0;

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

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

                id[i][j] = (i - 1) * m + j;

        for(i = 0 ; i <= n * m ; i ++ ) f[i] = i;

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

        {

            scanf("%s" , str + 1);

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

            {

                switch(str[j])

                {

                    case 'L': link(id[i][j] , id[i][j - 1]); break;

                    case 'R': link(id[i][j] , id[i][j + 1]); break;

                    case 'U': link(id[i][j] , id[i - 1][j]); break;

                    case 'D': link(id[i][j] , id[i + 1][j]); break;

                    default: v[id[i][j]] = ++p , wx[p] = i , wy[p] = j;

                }

            }

        }

        if(flag) puts("0");

        else

        {

            memset(a , 0 , sizeof(a));

            for(i = 1 ; i <= p ; i ++ )

            {

                a[i][i] += 4;

                a[i][v[find(id[wx[i]][wy[i] - 1])]] -- ;

                a[i][v[find(id[wx[i]][wy[i] + 1])]] -- ;

                a[i][v[find(id[wx[i] - 1][wy[i]])]] -- ;

                a[i][v[find(id[wx[i] + 1][wy[i]])]] -- ;

            }

            for(i = 1 ; i <= p ; i ++ )

                for(j = 1 ; j <= p ; j ++ )

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

            for(i = 1 ; i <= p ; i ++ )

            {

                for(j = i ; j <= p ; j ++ )

                    if(a[i][j])

                        break;

                if(j > p) continue;

                if(j != i)

                {

                    d ^= 1;

                    for(k = i ; k <= p ; k ++ )

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

                }

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

                t = pow(a[i][i] , mod - 2);

                for(j = i ; j <= p ; j ++ ) a[i][j] = a[i][j] * t % mod;

                for(j = i + 1 ; j <= p ; j ++ )

                    for(t = a[j][i] , k = i ; k <= p ; k ++ )

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

            }

            for(i = 1 ; i <= p ; i ++ ) ans = ans * a[i][i] % mod;

            if(d) ans = (mod - ans) % mod;

            printf("%lld\n" , ans);

        }

    }

    return 0;

}

相关文章