5.1模拟赛 T3 记录

题面

首先显然我们可以把序列变成几段连续段，如果连续段中有一个数不一样，显然不满足了。

现在就要求使得这几个连续段都独立不能连成一个大段地方案数，考虑容斥。

考虑进行连续段 \(dp\)，套路的，我们只要确认一个段最小的数是什么就可以知道整个段的值域，所以我们只需要确定连续段之间的大小关系就可以确定所有段的值域。

考虑设置 \(dp_{i,j,0/1}\) 表示考虑了前 \(i\) 段，总共形成至多 \(j\) 个独立段，最后一段是否是单个数。（因为单个数后面接的段可以是上升也可以是下降）

转移就考虑是否钦定这一段和前一段连成一个大段，不然大小排名有 \(j\) 种选择，最后容斥即可。

#include <bits/stdc++.h>

using namespace std;

const int maxn=2005;
const int mod=998244353;
int a[maxn],dp[maxn][maxn][3];//表示处理前 i 段，最多连成 j 段，最后一段是否只有一个数。
int b[maxn],cnt=0;

int main(){
	
	int n;
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++){
		b[++cnt]=a[i];
		int t=a[i]-1,j=i;
		while(t){
			j++;
			if(a[j]!=a[i]){
				puts("0");
				return 0;
			}
			t--;
		}
		i=j;
	}
	
	dp[1][1][b[1]>1]=(b[1]>1?2:1);
	
	for(int i=2;i<=cnt;i++){
		int tt=(b[i]>1);
		for(int j=1;j<=i;j++){
			dp[i][j][tt]=(dp[i][j][tt]+1ll*(tt+1)*j%mod*(dp[i-1][j-1][0]+dp[i-1][j-1][1])%mod)%mod;
			dp[i][j][1]=(dp[i][j][1]+(2ll*dp[i-1][j][0]%mod+dp[i-1][j][1])%mod)%mod;
		}
	}
	
	int res=0;
	
	for(int i=cnt;i>=1;i--){
		if((cnt-i)&1) res=(1ll*res-dp[cnt][i][0]+mod-dp[cnt][i][1]+mod)%mod;
		else res=(res+(dp[cnt][i][0]+dp[cnt][i][1])%mod)%mod;
	}
	
	printf("%d\n",res);
	
	return 0;
}