BZOJ 4031 [HEOI2015] 小 Z 的房间

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

题意：一个包含 n*m 个格子的网格图，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案。答案对 10⁹ 取模。

显然建模后求生成树个数即可，

度数矩阵 ：D[x][x] 表示点 x 的度数，其它元素为 0
邻接矩阵 ：A[x][y] 代表 x 到 $j$ 是否有边。有边则为 $1$ ，否则为 0.

基尔霍夫矩阵：C=D-A.

Matrix-Tree 定理 ：对于一个基尔霍夫矩阵，随意去掉第 r 行和第 r 列 ($r\in [1,n]$)，留下的这个矩阵的行列式的 绝对值 ，就是生成树的个数。

对于质数模意义下的矩阵行列式计算，显然直接处理逆元即可，那么一般的合数呢？如此题

高精度分数？中国剩余定理？都不是很优雅的解决方案

根据代数知识，矩阵的任意一行减去另一行的倍数，行列式不变。交换两行，行列式变负。所以我们可以用一种类似辗转相除法的姿势，不断地减，交换，直到被消元行被减到 0 为止，时间复杂度是 log 级别的，且在模意义下的实现是很方便的。

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 1000000000
#define ll long long
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
ll D[110][110];
int n,m,cnt,a[11][11];
char mp[11][11];
ll det(int n)
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    D[i][j]=(D[i][j]+mod)%mod;
    int f=1;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    {
        ll A=D[i][i],B=D[j][i];
        while(B)
        {
            ll t=A/B;A%=B;swap(A,B);
            for(int k=1;k<=n;k++)
            D[i][k]=(D[i][k]-D[j][k]*t%mod+mod)%mod;
            for(int k=1;k<=n;k++)
            swap(D[i][k],D[j][k]);
            f=-f; 
        }
    }
    ll ans=1;
    for(int i=1;i<=n;i++)
    ans=ans*D[i][i]%mod;
    if(f==-1)ans=(mod-ans)%mod;
    return ans;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    scanf("%s",mp[i]+1);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(mp[i][j]=='.')a[i][j]=++cnt;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(mp[i][j]=='.')
    for(int k=0;k<4;k++)
    {
        int x=i+xx[k],y=j+yy[k];
        if(x<1||y<1||x>n||y>m||mp[x][y]!='.')continue;
        int u=a[i][j],v=a[x][y];
        D[u][u]++;D[u][v]--;
    }
    printf("%lld\n",det(cnt-1));
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define mod 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

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

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

ll D[110][110];

int n,m,cnt,a[11][11];

char mp[11][11];

ll det(int n)

{

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

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

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

int f=1;

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

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

{

ll A=D[i][i],B=D[j][i];

while(B)

{

ll t=A/B;A%=B;swap(A,B);

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

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

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

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

f=-f;

}

ll ans=1;

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

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

if(f==-1)ans=(mod-ans)%mod;

return ans;

}

int main()

{

n=read(),m=read();

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

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

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

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

if(mp[i][j]=='.')a[i][j]=++cnt;

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

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

if(mp[i][j]=='.')

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

{

int x=i+xx[k],y=j+yy[k];

if(x<1||y<1||x>n||y>m||mp[x][y]!='.')continue;

int u=a[i][j],v=a[x][y];

D[u][u]++;D[u][v]--;

}

printf("%lld\n",det(cnt-1));

}

zgz233

BZOJ 4031 [HEOI2015] 小 Z 的房间

BZOJ 2115 [Wc2011] Xor

BZOJ 4596 [Shoi2016] 黑暗前的幻想乡

l1ll5

Comments | NOTHING

zgz233