代码

#include<cstdio>
#include<cstring>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define Mod 998244353

int n;
int a[600001];

// straight-forward DP
// f[i][j] : [1..i] maximum=j
// f[i][j] -> f[i+1][k](k>j) , f[i+1][j](fill in [minimum+1] && j>i)
// f[i][j] = f[i-1][k](k<j) + f[i-1][j](j>=i)
int f[1001][1001];
int vis[1001];
void solve1(){
	memset(vis,0,sizeof vis);
	memset(f,0,sizeof f);
	int ok=1,oo,maxq=a[1]; vis[a[1]]=1;
	F(j,a[1]+1,n) f[1][j]=1;
	F(i,2,n){
		f[i][i]=(f[i-1][i-1]+f[i-1][i])%Mod;
		F(j,i+1,n) f[i][j]=(f[i][j-1]+f[i-1][j])%Mod;
		oo=1;
		if(a[i]<maxq){
			F(j,1,a[i]-1) if(!vis[j]) {oo=0; break;}
		}
		else maxq=a[i];
		if(ok){
			F(j,maxq+1,n) f[i][j]=(f[i][j]+1)%Mod;
			ok=oo;
		}
		vis[a[i]]=1;
	}
	printf("%d\n",f[n][n]);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		F(i,1,n) scanf("%d",a+i);
		if(n<=1000) solve1();
	}
	return 0;
}

评测结果