LGP6008题解

题意有点儿绕？

容易发现，题意相当于在说，如果某一格有水，那么 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);

}

巴特西

LGP6008题解

最新文章

热门文章