题解 P4111 【[HEOI2015]小 Z 的房间】

· · 题解

题目明显是个矩阵树定理。我主要讲一下如何处理一些细节。

有两个麻烦的地方：

  1. 题目中有一些地方不能走，那么在矩阵中就不能给它留位置，否则对角线上有地方会是 0。

    也就是说矩阵的边长不能是 n\times m，而是 n\times m -\text{柱子数}。

  2. 模数不是质数，高斯消元中不能用逆元。

    这就要用到一种神奇的方法——辗转相除法。

    设现在我们枚举了矩阵中的两行 i、j：

    a_{i,i}&a_{i,i+1}&\cdots&a_{i,n}\\ \\ a_{j,i}&a_{j,i+1}&\cdots&a_{j,n} \end{bmatrix}

    根据高斯消元，我们现在要做的是把每一个 a_{i,k}（i\leq k\leq n）乘上 \dfrac{a_{j,i}}{a_{i,i}}，然后再把每一个 a_{j,k}（i\leq k\leq n）减去 a_{i,k}，然后就能消去 a_{j,i}。

    形式化地说，就是对于任意的 i\leq k\leq n，a_{j,k}\gets \left(a_{j,k}-a_{i,k}\dfrac{a_{j,i}}{a_{i,i}}\right)。

    平常的高斯消元可以用 double 直接算，但是要取模。而正常的模质数也可以用逆元处理 \dfrac{1}{a_{i,i}}。但是这一题模数不是质数，就不能用逆元，只能用辗转相除法：

    考虑到我们的目的就是消掉 a_{j,i}。整理一下条件：我们可以对矩阵进行两行交换，一行减去另一行的若干倍。

    发现这也满足辗转相除的性质：

    我们可以把 a_{i,k} 减去 a_{j,k}\lfloor\dfrac{a_{i,i}}{a_{j,i}}\rfloor（i\leq k\leq n），然后再交换第 i 行和第 j 行。对于 a_{i,i} 和 a_{j,i}，发现这就和辗转相除中的操作 (a_{i,i},a_{j,i})\rightarrow(a_{j,i},a_{i,i}\bmod a_{j,i}) 一样。

    那么辗转相除到最后，肯定有 a_{j,i}=0，也满足了我们的目的。

    代码：

    for(int i=1;i<tot;i++)
{
    for(int j=i+1;j<tot;j++)
    {
        //枚举出矩阵中的两行i、j
        while(a[j][i])//直到a[j][i]=0时，也就是达成目的时才停止
        {
            ll d=a[i][i]/a[j][i];
            for(int k=i;k<tot;k++)
                a[i][k]=(a[i][k]-d*a[j][k]%mod+mod)%mod;
            swap(a[i],a[j]);//交换两行
            ans=-ans;//交换矩阵的两行行列式要变号
        }
    }
}

    至于为什么可以边模边辗转相除，也就是为什么 (a_{i,i},a_{j,i})\rightarrow(a_{j,i},a_{i,i}\bmod a_{j,i}) 等同于 (a_{i,i},a_{j,i})\rightarrow\left(a_{j,i}\bmod p,\left(a_{i,i}-a_{j,i}\lfloor\dfrac{a_{i,i}}{a_{j,i}}\rfloor\right)\bmod p\right)。

    首先有一开始 a_{i,i} 和 a_{j,i} 的绝对值均小于 p，而 a_{i,i}\bmod a_{j,i}<a_{j,i}。所以可以保证，在整个辗转相除的过程中，a_{i,i} 和 a_{j,i} 的绝对值均小于 p。

    此时 a_{i,i} 和 a_{j,i} 模完 p 后还是它本身，可以看做整个辗转相除过程中，a_{i,i} 和 a_{j,i} 根本没有模过 p。那么边模边辗转相除是完全没有问题的。

然后所有的麻烦都被我们处理完了。

代码如下：

#include<bits/stdc++.h>

#define N 110
#define ll long long
#define mod 1000000000

using namespace std;

int n,m,tot,id[N][N];
int fx[]={0,1},fy[]={1,0};
ll ans=1,a[N][N];

void work()//细节2，注释详见上面的代码
{
    for(int i=1;i<tot;i++)
    {
        for(int j=i+1;j<tot;j++)
        {
            while(a[j][i])
            {
                ll d=a[i][i]/a[j][i];
                for(int k=i;k<tot;k++)
                    a[i][k]=(a[i][k]-d*a[j][k]%mod+mod)%mod;
                swap(a[i],a[j]);
                ans=-ans;
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char s[15];
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            if(s[j]=='.')
                id[i][j]=++tot;//细节1，只有这个点不是柱子才算进矩阵的编号
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!id[i][j]) continue;
            int u=id[i][j];
            for(int k=0;k<2;k++)
            {
                int xx=i+fx[k],yy=j+fy[k];
                if(!id[xx][yy]) continue;
                int v=id[xx][yy];
                a[u][u]++,a[v][v]++;
                a[u][v]--,a[v][u]--;
            }
        }
    }
    work();
    for(int i=1;i<tot;i++)
        ans=ans*a[i][i]%mod;
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}