LGP6008题解
阅读原文时间:2023年07月08日阅读:4

题意有点儿绕?

容易发现,题意相当于在说,如果某一格有水,那么 ban 掉上一行后,让与其连同的所有格子被画上水。

所以我们从上到下枚举行,依次 ban 掉每一行,然后数连通块个数即可。

需要注意的是不连通的部分答案应该相乘,连通的部分答案应该相加。

但是这样做是 \(O(n^2m)\) 的,需要优化。

从上到下 ban 掉每一行的过程有点儿像删边,那么我们反过来加边。这样用并查集是很容易维护连通块个数的。

复杂度 \(O(nm\alpha(nm))\)。

加边时,如果合并了两个连通块,两列之间的方案是互不影响的,需要乘起来,在每一行合并结束后需要让每个连通块的方案数加 \(1\)。(全选)

人懒写了 \(O(nm\log nm)\) 就跑路了(

#include<cstdio>
const int M=1005,mod=1e9+7;
int n,m,cnt,id[M][M],f[M*M],siz[M*M],sum[M*M];char s[M][M];int ans(1);
inline int Find(const int&u){
    return f[u]==u?u:f[u]=Find(f[u]);
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
    for(int i=2;i<n;++i)for(int j=2;j<m;++j)id[i][j]=++cnt,f[id[i][j]]=id[i][j],sum[id[i][j]]=1;
    for(int i=n-1;i>1;--i){
        for(int j=2;j<m;++j)if(s[i][j]=='.'&&s[i][j-1]=='.')f[Find(id[i][j])]=Find(id[i][j-1]);
        for(int j=2;j<m;++j)if(s[i][j]=='.'&&s[i+1][j]=='.'&&Find(id[i][j])!=Find(id[i+1][j])){
            const int x=Find(id[i][j]),y=Find(id[i+1][j]);
            sum[x]=1ll*sum[x]*sum[y]%mod;f[y]=x;
        }
        for(int j=2;j<m;++j)if(s[i][j]=='.'&&Find(id[i][j])==id[i][j])++sum[id[i][j]];
    }
    for(int i=2;i<n;++i)for(int j=2;j<m;++j){
        if(s[i][j]=='.'&&Find(id[i][j])==id[i][j])ans=1ll*ans*sum[id[i][j]]%mod;
    }
    printf("%d",ans);
}