Sprinklers 2: Return of the Alfalfa P

条件是: 每个点都要被覆盖，且不能被两种覆盖，那么最后覆盖的情况一定是形如下图的

其中红色和黄色的点表示关键的覆盖点，其他点按照其所属的颜色可以选择放或者不放

那么考虑从上到下，依次对于每一层$dp$竖线的位置，那么有两种转移方法

1.保留上层竖线，两边空白位置的可行点用2的幂次乘进答案即可

2.将当前层的竖线右移，必须选择两个位置，其他位置依然按照2的幂次加入答案

直接转移是$O(n^3)$的，对于第2中转移应用前缀和优化即可做到$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }
 
char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}
 
const int N=2e3+10,P=1e9+7;
 
int n;
char A[N][N];
 
int dp[N][N];
int c[N][N],rc[N][N]; 
int Pow[N];
 
int main(){
    n=rd();
    rep(i,1,n) scanf("%s",A[i]+1);
    rep(i,1,n) rep(j,1,n) c[i][j]=c[i][j-1]+(A[i][j]=='.');
    rep(i,1,n) drep(j,n,1) rc[i][j]=rc[i][j+1]+(A[i][j]=='.');
    rep(i,Pow[0]=1,n) Pow[i]=Pow[i-1]*2%P;
    dp[0][0]=1;
    rep(i,1,n) {
        int s=0;
        rep(j,0,n) {
            dp[i][j]=(dp[i][j]+1ll*dp[i-1][j]*Pow[c[i][j]+rc[i-1][j+1]])%P;
            // 空白位置的可行点按照2的幂次加入答案
            if(A[i][j]!='W') dp[i][j]=(dp[i][j]+1ll*s*(j?Pow[c[i][j]-1]:1))%P;
            //把两个强制选择的关键点分开，在累入前缀和 和 从前缀和中拿出时考虑即可
            
            if(A[i-1][j+1]!='W') s=(s+1ll*dp[i-1][j]*(i>1&&j<n?Pow[rc[i-1][j+1]-1]:1))%P;
        }
    }
    int ans=0;
    rep(i,0,n) if(A[n][i+1]!='W') ans=(ans+1ll*(i<n?Pow[rc[n][i+1]-1]:1)*dp[n][i])%P;
    printf("%d\n",ans);
}