3 条题解

  • 4
    @ 2026-10-28 8:49:24

    每层每个连通块开个点,发现这个跑出来形如一个森林,跑个没有上司的舞会状物做完了。

    #include<iostream>
    #include<algorithm>
    #include<vector>
    #define int long long
    using namespace std;
    const int N=1e3+7,MOD=1e9+7;
    int n,m,g[N][N],fa[N],ans=1,col[N][N],vis[N];
    int dp[N][N][2],root[N][N];
    vector<int> t[N];
    int find(int x){
    	if(fa[x]==x) return x;
    	return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
    	int fx=find(x),fy=find(y);
    	if(fx==fy) return ;
    	fa[fx]=fy;
    }
    int pw(int x,int b){
    	int res=1;
    	for(;b;b>>=1,x=x*x%MOD) if(b&1) res=res*x%MOD;
    	return res;
    }
    signed main(){
    //	freopen("ex.in","r",stdin);
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			char c;
    			cin>>c;
    			if(c=='#') g[i][j]=0;
    			else g[i][j]=1;
    		}
    	}
    	for(int i=n-1;i>1;i--){
    		for(int j=2;j<m;j++)
    			fa[j]=g[i][j]?j:0;
    		for(int j=2;j<m;j++)
    			if(g[i][j] && g[i][j-1])
    				merge(j,j-1);
    		for(int j=2;j<m;j++){
    			if(t[j].empty()) continue;
    			int u=t[j][0];
    			for(int v : t[j]) merge(u,v);
    		}
    		for(int j=2;j<m;j++){
    			t[j].clear();
    			t[j].shrink_to_fit();
    		}
    		for(int j=2;j<m;j++){
    			if(g[i-1][j] && g[i][j]){
    				int f=find(j);
    				t[f].push_back(j); 
    			}
    		}
    		for(int j=2;j<m;j++){
    			col[i][j]=find(j);
    			root[i][col[i][j]]=1;
    			int x=col[i][j];
    			dp[i][x][0]=dp[i][x][1]=1;
    //			cout<<col[i][j]<<' ';
    		}
    //		cout<<'\n';
    	}
    	for(int i=n-1;i>1;i--){
    		for(int j=1;j<=m;j++) vis[j]=0;
    		for(int j=2;j<m;j++){
    			int x=col[i][j],y=col[i+1][j];
    			if(x && y && !vis[y]){
    //				cout<<"# "<<x<<' '<<y<<' '<<dp[i+1][y][0]+dp[i+1][y][1]<<'\n';
    				(dp[i][x][1]*=dp[i+1][y][1])%=MOD;
    				(dp[i][x][0]*=(dp[i+1][y][0]+dp[i+1][y][1]))%=MOD;
    				root[i+1][y]=0;
    				vis[y]=1;
    			}
    		}
    	}
    	for(int i=2;i<n;i++)
    		for(int j=2;j<m;j++) 
    			if(root[i][j]){
    				if(dp[i][j][0]+dp[i][j][1]) 
    					ans=ans*(dp[i][j][0]+dp[i][j][1])%MOD;
    			}
    	cout<<ans;
    	return 0;
    } 
    

信息

ID
949
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
36
已通过
12
上传者