2023-07-17 14:24:51
发布于：广东
85阅读
0回复
0点赞
可恶啊，这个代码如果没mle的话绝对AC，哪个好心人帮帮我。。。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=155;
const LL TT=1e9+7;
int N,s[maxn];
LL f[maxn][maxn][maxn][2][2],g[maxn][maxn][maxn][2][2];
char ch[maxn];
LL ans=0;
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int get(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])%TT-g[i][y][p-1][l][r])%TT+g[i][x-1][p-1][l][r]+TT)%TT;
}
int main(){
N=read();
for(int i=1;i<=N;i++){
scanf("%s",ch+1);
for(int j=1;j<=N;j++) s[j]=s[j-1]+(ch[j]=='G');
for(int l=N;l>=1;l--)
for(int r=l;r<=N;r++)if(s[r]-s[l-1]==r-l+1){
f[i][l][r][0][0]=1+get(i-1,l,r,l,r,0,0);
f[i][l][r][0][1]=(get(i-1,l,r,r+1,N,0,0)+get(i-1,l,r,r,N,0,1))%TT;
f[i][l][r][1][0]=(get(i-1,1,l-1,l,r,0,0)+get(i-1,1,l,l,r,1,0))%TT;
f[i][l][r][1][1]=((get(i-1,1,l,r,N,1,1)+get(i-1,1,l-1,r+1,N,0,0))%TT+(get(i-1,1,l-1,r,N,0,1)+get(i-1,1,l,r+1,N,1,0))%TT)%TT;
for(int ii=0;ii<=1;ii++)
for(int jj=0;jj<=1;jj++)ans=(ans+f[i][l][r][ii][jj])%TT;
}
for(int p=0;p<=1;p++)
for(int q=0;q<=1;q++)
for(int x=1;x<=N;x++)
for(int y=1;y<=N;y++)
g[i][x][y][p][q]=(((g[i][x-1][y][p][q]+g[i][x][y-1][p][q])%TT-g[i][x-1][y-1][p][q])%TT+f[i][x][y][p][q])%TT;
}
printf("%lld\n",(ans+TT)%TT);
return 0;
}
有帮助，赞一个