LGP6008题解

题意有点儿绕？

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

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

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

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

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

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

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

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

#include
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;i1;--i){
		for(int j=2;j