题意有点儿绕?
容易发现,题意相当于在说,如果某一格有水,那么 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);
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章