感觉很难的区间dp，主要是状态难想
/* 对于一个区间[i,j]，设其最小的颜色编号是c=Min[i,j],那么该区间显然有一大段是以c为底的 设这个颜色在该区间出现位置的两端是L[c],R[c],那么我们枚举该区间以c为底的颜色段[l,r] 显然l<=L[c],r>=R[c],则该区间被分为了五段：[i,l-1],[l,L[c]-1],[L[c],R[c]],[R[c]+1,r],[r+1,j] 1，5 段是不以c为底色的段， 2，4 是以c为底，但被其他颜色覆盖的段， 3 是被c包围，中间还有其他颜色的段 需要预处理Min[i,j],nxt[i] 枚举区间[i,j],再枚举l：[i,L[c]-1],r:[R[c]+1,j],最后处理中间的[L[c],R[c]],即遍历所有被c隔开的段落 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define mod 998244353 #define N 1007 #define M 2000005 inline ll fk(ll x){return x>=mod?x-mod:x;} ll n,m,a[M],b[M],tot; ll L[N],R[N],Min[N][N],f[N][N]; int pos[N],nxt[N]; int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i]; } for(int i=1;i<=m;i++) if(a[i]!=a[i-1])b[++tot]=a[i]; if(tot>2*n){cout<<'0'<<' ';return 0;} m=tot;for(int i=1;i<=m;i++)a[i]=b[i]; //处理序列自动机 for(int i=0;i<=m;i++)pos[i]=m+1; for(int i=m;i>=1;i--){ nxt[i]=pos[a[i]]; pos[a[i]]=i; } //处理L,R数组 memset(L,0x3f,sizeof L); for(ll i=1;i<=m;i++){ L[a[i]]=min(L[a[i]],i); R[a[i]]=max(R[a[i]],i); } //处理Min数组 memset(Min,0x3f,sizeof Min); for(int i=1;i<=m;i++) for(int j=i;j<=m;j++) for(int k=i;k<=j;k++) Min[i][j]=min(Min[i][j],a[k]); //初始化 for(int i=0;i<=m+1;i++){ if(i && i<=m && L[a[i]]==i && R[a[i]]==i)f[i][i]=1;//没被隔断的区间 for(int j=0;j<=m+1;j++) if(i>j)f[i][j]=1; } for(int k=1;k<m;k++) for(int i=1;i+k<=m;i++){ int p=Min[i][i+k];if(p>N)continue; if(L[p]<i || R[p]>i+k)continue;//p的范围超过了[i,i+k],说明这个区间不用计算 ll cntl=0,cntr=0,sum=1; for(int j=i;j<=L[p];j++)//枚举[i,L[p]] cntl=fk(cntl+f[i][j-1]*f[j][L[p]-1]%mod); for(int j=R[p];j<=i+k;j++)//枚举[R[p],j] cntr=fk(cntr+f[R[p]+1][j]*f[j+1][i+k]%mod); for(int j=L[p];j<R[p];j=nxt[j])//枚举[L[p],R[p]]中被p隔开的所有段 sum=sum*f[j+1][nxt[j]-1]%mod; f[i][i+k]=cntl*cntr%mod*sum%mod; } cout<<f[1][m]<<' '; }