3 条题解
-
4
每层每个连通块开个点,发现这个跑出来形如一个森林,跑个没有上司的舞会状物做完了。
#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
- 上传者