Submission #34044850

---

Source Code Expand

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
template<int P>
class mod_int{
	using Z=mod_int;
private:
	static int mo(int x){return x<0?x+P:x;}
public:
	int x;
	int val()const{return x;}
	mod_int():x(0){}
	template<class T>mod_int(const T&x_):x(x_>=0&&x_<P?static_cast<int>(x_):mo(static_cast<int>(x_%P))){}
	bool operator==(const Z&rhs)const{return x==rhs.x;}
	bool operator!=(const Z&rhs)const{return x!=rhs.x;}
	Z operator-()const{return Z(x?P-x:0);}
	Z pow(long long k)const{
		Z res=1,t=*this;
		while(k){
			if(k&1)res*=t;
			if(k>>=1)t*=t;
		}
		return res;
	}
	Z&operator++(){
		x<P-1?++x:x=0;
		return *this;
	}
	Z&operator--(){
		x?--x:x=P-1;
		return *this;
	}
	Z operator++(int){
		Z ret=x;
		x<P-1?++x:x=0;
		return ret;
	}
	Z operator--(int){
		Z ret=x;
		x?--x:x=P-1;
		return ret;
	}
	Z inv()const{
#ifdef xay5421
		assert(x!=0);
#endif
		return pow(P-2);
	}
	Z&operator+=(const Z&rhs){
		(x+=rhs.x)>=P&&(x-=P);
		return *this;
	}
	Z&operator-=(const Z&rhs){
		(x-=rhs.x)<0&&(x+=P);
		return *this;
	}
	Z&operator*=(const Z&rhs){
		x=1ULL*x*rhs.x%P;
		return *this;
	}
	Z&operator/=(const Z&rhs){
		return *this*=rhs.inv();
	}
#define setO(T,o) friend T operator o(const Z&lhs,const Z&rhs){Z res=lhs;return res o##=rhs;}
	setO(Z,+)setO(Z,-)setO(Z,*)setO(Z,/)
#undef setO
};
const int P=998244353;
using Z=mod_int<P>;
const int N=5005;
int n,a[N],aa[N],ok[N];
Z f[2][N],tag[N];
void deal(int i){
	fill(ok+1,ok+n+1,0);
	int mx=0;
	per(j,i,1){
		mx=max(mx,a[j]);
		ok[mx]=1;
	}
	mx=0;
	rep(j,i,n){
		mx=max(mx,a[j]);
		ok[mx]=1;
	}
	rep(j,1,n)if(!ok[j]){
		f[i&1][j]=0;
	}
	
}
int main(){
	rd(n);
	rep(i,1,n)rd(a[i]);
	rep(i,1,n)aa[a[i]]=i;
	int mx=0;
	rep(i,1,n){
		mx=max(mx,a[i]);
		f[1][mx]=1;
	}
	rep(i,1,n-1){
		rep(j,0,n+1)f[(i+1)&1][j]=0;
		rep(j,0,n+1)tag[j]=0;
		rep(j,1,n)if(f[i&1][j].val()){
			tag[j]+=f[i&1][j];
			{
				int j_=a[i+1];
				if(aa[j_]>=aa[j]){
					f[(i+1)&1][j_]+=f[i&1][j];
				}
			}
			if(j>=a[i+1])f[(i+1)&1][j]-=f[i&1][j];
			f[(i+1)&1][j]+=f[i&1][j];
		}
		rep(j,1,n){
			if(j)tag[a[j]]+=tag[a[j-1]];
			if(a[j]>=a[i+1]+1){
				f[(i+1)&1][a[j]]+=tag[a[j]];
			}
		}
		deal(i+1);
	}
	Z ans=0;
	rep(j,1,n)ans+=f[n&1][j];
	printf("%d\n",ans.val());
	return 0;
}

Submission Info

Judge Result