记录编号	600491	评测结果	ATTTEEEEEE
题目名称	4139.cake	最终得分	10
用户昵称	徐诗畅	是否通过	未通过
代码语言	C++	运行时间	7.461 s
提交时间	2025-05-05 15:04:30	内存使用	5.25 MiB

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=505;
int n,m,pre[N][N],mp[N*N];
long long dp[N],dp2[N];
string cake[N];
int main(){
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 0;i<n;i++) cin>>cake[i];
    for (int i = 1;i<=n;i++){
        for (int j = 1;j<=m;j++){
            pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
            if(cake[i-1][j-1]=='Y'){
                pre[i][j]++;
            }
        }
    }
    dp[0]=1;
    for(int i = 1;i<=n;i++){
        for(int j=0;j<i;j++){
            memset(dp2,0,sizeof(dp2)); dp2[0]=1;
            memset(mp,0,sizeof(mp)); mp[0]=1;
            int sum=0;
            for(int k=1;k<=m;k++){
                sum+=pre[i][k]-pre[j][k]-pre[i][k-1]+pre[j][k-1];
                if(sum>=2&&mp[sum-2])
                dp2[k]=mp[sum-2];
                mp[sum]=(mp[sum]+dp2[k])%mod;
            }
            dp[i] =(dp[i]+dp[j]*dp2[m]%mod)%mod;
        }
    }
    printf("%lld",dp[n]);
    return 0;
}