记录编号	600540	评测结果	AAAAAAAAAA
题目名称	4139.cake	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	1.772 s
提交时间	2025-05-06 20:12:24	内存使用	50.90 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,b[2000005],f[2000005],ts,t[2000005],ss,M=998244353,pp;
vector<long long>v[2000005];
string s;
int main(){
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>s;
        for(long long j=1;j<=m;j++) if(s[j-1]=='Y') v[i].push_back(j),b[i]++;
    }
    for(long long i=1;i<=n;i++){
        ts=0,f[0]=1;
        for(long long j=1;j<=m;j++) t[j]=0;
        for(long long j=i-1,pp=0;j>=0;j--){
            ts+=b[j+1];
            ss=pp=1;
            for(long long k=0;k<v[j+1].size();k++) t[v[j+1][k]]++;
            if(ts&1||!ts) continue;
            for(long long k=1,tp=0,fp=0;k<=m;k++){
                if(t[k]>2){pp=0; break;}
                if(t[k]==2){
                    if(tp%2){pp=2; break;}
                    if(fp) ss*=(k-fp)%M,ss%=M;
                    tp+=2,fp=k;
                }else if(t[k]){
                    if(tp%2==0&&tp) ss*=(k-fp)%M,ss%=M;
                    tp++,fp=k;
                }
            }
            if(!pp) break;
            if(pp==2) continue; 
            f[i]+=f[j]%M*ss%M;
            f[i]%=M;
        }
    }
    cout<<f[n]%M;
    return 0;
}