题目链接
这题我用的排除法，首先可以计算出所有灯的数量 k k k，则总情况数即为 k ∗ 2 k k*2^k k∗2k，对每一盏灯，只需要减去使其不亮的情况即可，即算出上下左右的联通的灯的数量 x x x，则总情况数就是 2 k − x 2^{k-x} 2k−x，答案就是 k ∗ 2 k − ∑ i = 1 k 2 k − x i k*2^k-\sum_{i=1}^k 2^{k-x_i} k∗2k−∑i=1k2k−xi 即可，AC代码如下:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+5; const ll mod=1e9+7; ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;} int h,w; ll k,ans,u[N][N],d[N][N],l[N][N],r[N][N]; char g[N][N]; int main() { scanf("%d%d",&h,&w); for(int i=1;i<=h;i++){ getchar(); for(int j=1;j<=w;j++){ scanf("%c",&g[i][j]); if(g[i][j]=='.') k++; } } for(int j=1;j<=w;j++){ for(int i=1;i<=h;i++){ if(g[i][j]=='#') u[i][j]=0; else u[i][j]=u[i-1][j]+1; } } for(int j=1;j<=w;j++){ for(int i=h;i>=1;i--){ if(g[i][j]=='#') d[i][j]=0; else d[i][j]=d[i+1][j]+1; } } for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ if(g[i][j]=='#') l[i][j]=0; else l[i][j]=l[i][j-1]+1; } } for(int i=1;i<=h;i++){ for(int j=w;j>=1;j--){ if(g[i][j]=='#') r[i][j]=0; else r[i][j]=r[i][j+1]+1; } } ans=power(2,k)*k%mod; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) if(g[i][j]=='.') ans-=power(2,k-(u[i][j]+d[i][j]+l[i][j]+r[i][j]-3)); if(ans<0) ans=(mod-(-ans)%mod)%mod; cout<<ans; return 0; }