题解(用命换的)
2023-07-26 13:56:12
发布于:河北
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 155
#define P 1000000007
using namespace std;
int n,u[N],f[N][N][N][2][2],g[N][N][N][2][2];char s[N];
int w(int i,int x,int y,int p,int q,int l,int r){
return (((g[i][y][q][l][r]-g[i][x-1][q][l][r])%P-g[i][y][p-1][l][r])%P+g[i][x-1][p-1][l][r])%P;
}
int main(){
scanf("%d",&n);int ans=0;
rep(i,1,n){
scanf("%s",s+1);
rep(j,1,n)u[j]=u[j-1]+(s[j]=='G');
pre(l,n,1)rep(r,l,n)if(u[r]-u[l-1]==r-l+1){
f[i][l][r][0][0]=1+w(i-1,l,r,l,r,0,0);
f[i][l][r][0][1]=(w(i-1,l,r,r+1,n,0,0)+w(i-1,l,r,r,n,0,1))%P;
f[i][l][r][1][0]=(w(i-1,1,l-1,l,r,0,0)+w(i-1,1,l,l,r,1,0))%P;
f[i][l][r][1][1]=((w(i-1,1,l,r,n,1,1)+w(i-1,1,l-1,r+1,n,0,0))%P+
(w(i-1,1,l-1,r,n,0,1)+w(i-1,1,l,r+1,n,1,0))%P)%P;
rep(x,0,1)rep(y,0,1)(ans+=f[i][l][r][x][y])%=P;
}
rep(p,0,1)rep(q,0,1)rep(x,1,n)rep(y,1,n)
g[i][x][y][p][q]=(((g[i][x-1][y][p][q]+g[i][x][y-1][p][q])%P-g[i][x-1][y-1][p][q])%P+f[i][x][y][p][q])%P;
}
printf("%d\n",(ans+P)%P);
return 0;
}
全部评论 1
你是7kbyte吗
2023-08-16 来自 广东
0
有帮助,赞一个