Long Colorful Strip
中间如果有那些地方看不懂，可以先去看看前面一道，这是我的题解。
首先，每一次染色，最多把一整段连续的同色格子，分成了三段。
并且，明显我们可以把连续的同色格子，直接看作一个。
这就意味着，在这么压缩后，有 \(m<2n\)。
这就意味着 \(O(m^3)\) 的复杂度是可以接受的。
还是考虑和前一道题一样的 DP。
但是这题，并非所有的 \(f[i,j]\) 都是合法的；只有对于每一种颜色，它所有的格子要么全都在段内，要么全都在段外，这样的 \(f[i,j]\) 才是合法的。因为，两个格子只要从什么时候开始颜色不一样了，那它们的颜色也会一直不一样下去。
考虑如何转移。
因为每种颜色都可能出现了不止一次，所以对于一种颜色 \(c\)，我们有必要记录它出现的最左端 \(mn_c\) 与最右端 \(mx_c\) 。
则转移时的左右两端仍然可以采取和上一问一模一样的转移方式，即
\[f[i,j]=(\sum\limits_{k=i}^{mn_{mp}}f[i,k-1] \times f[k,mn_{mp}-1]) \times (\sum\limits_{l=mx_{mp}}^jf[mx_{mp}+1,l] \times f[l+1,j])
\]
同时，对于区间 \([mn_{mp},mx_{mp}]\) 内的非 \(mp\) 的所有连续格子段 \([p_x,q_x]\)，我们也都应该计算它们的贡献。
因此我们最终得到的是
\[f[i,j]=(\sum\limits_{k=i}^{mn_{mp}}f[i,k-1]*f[k,mn_{mp}-1])*(\sum\limits_{l=mx_{mp}}^jf[mx_{mp}+1,l]*f[l+1,j])*\prod f[p_x,q_x]
\]
复杂度仍是 \(O(n^3)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353,INF=0x3f3f3f3f;
const int N=1e3+100,M=1e6+100;
int n,m,a[M],f[N][N],mn[N],mx[N];
signed main(){
cin>>n>>m;memset(mn,INF,sizeof(mn));
for(int i=1;i<=m;i++){cin>>a[i];if(a[i]==a[i-1]) i--,m--;}
if(m>2*n){cout<<"0";return 0;}
for(int i=1;i<=m;i++) mx[a[i]]=max(mx[a[i]],i),mn[a[i]]=min(mn[a[i]],i);
for(int i=1;i<=m+1;i++) for(int j=0;j<i;j++) f[i][j]=1;
for(int l=1;l<=m;l++)
for(int i=1,j=i+l-1;j<=m;i++,j++){
int now=INF,A=0,B=0;
for(int k=i;k<=j;k++) now=min(now,a[k]);
if(mn[now]<i||mx[now]>j) continue;
for(int k=mn[now];k>=i;k--)(A+=(f[i][k-1]*f[k][mn[now]-1]%mod))%=mod;
for(int l=mx[now];l<=j;l++)(B+=(f[mx[now]+1][l]*f[l+1][j]%mod))%=mod;
f[i][j]=A*B%mod;
for(int p=mn[now]+1,q=mn[now];p<mx[now];){
while(q<j&&a[q+1]!=now) q++;
f[i][j]=f[i][j]*f[p][q]%mod;
q++;p=q+1;
}
}
cout<<f[1][m];
return 0;
}