题解

考虑从小到大插入，记$f(i,l,r,j)$表示当前插入了所有不大于$i$的数，且形成了$j$个$i$与$i$相邻的空位，且左端为$i$的真值为$l$，且右端为$i$的真值为$r$，此时，每个空位至少要插入一个$i+1$。 如果一个空位插入了$n$个$i+1$，那么新的序列会额外产生$n-1$个$i+1$与$i+1$相邻的空位。 如果上一轮在序列的最左或最右插入了至少$1$个$i$，那么插入$i+1$是可以选择在序列边界插入的，若不然，则序列边界不再能插入新的数。如果在边界插入$1$个$i+1$，则不产生空位，如果插入了$n$个$i+1$，那么新的序列会额外产生$n-1$个$i+1$与$i+1$相邻的空位。 不难发现： $f(i+1,0,0,a_{i+1}-j)=f(i,l,r,j)*C(a_{i+1}-1,j-1)$ $f(i+1,1,0,a_{i+1}-j-1)=f(i,1,r,j)*C(a_{i+1}-1,j)$ $f(i+1,0,1,a_{i+1}-j-1)=f(i,l,1,j)*C(a_{i+1}-1,j)$ $f(i+1,1,1,a_{i+1}-j-2)=f(i,1,1,j)*C(a_{i+1}-1,j+1)$ 注意到对于已知的$i$，$j$至多有$3$种状态，可以在$O(n)$复杂度内完成递推。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
using PII=std::pair<int,int>;
using i64=long long;
template<class T>
constexpr T power(T a,i64 b) {
    T res=1;
    for(;b;b/=2,a*=a){
        if(b%2)res*=a;
    }
    return res;
}

constexpr i64 mul(i64 a,i64 b,i64 p){
    i64 res=a*b-i64(1.L*a*b/p)*p;
    res%=p;
    if(res<0)res+=p;
    return res;
}

template<i64 P>
struct MLong{
    i64 x;
    constexpr MLong():x{}{}
    constexpr MLong(i64 x):x{norm(x % getMod())}{}
    
    static i64 Mod;
    constexpr static i64 getMod(){
        if(P>0)return P;
        else return Mod;
    }
    constexpr static void setMod(i64 Mod_){
        Mod=Mod_;
    }
    constexpr i64 norm(i64 x)const{
        if(x<0)x+=getMod();
        if(x>=getMod())x-=getMod();
        return x;
    }
    constexpr i64 val()const{
        return x;
    }
    explicit constexpr operator i64() const{
        return x;
    }
    constexpr MLong operator-() const{
        MLong res;
        res.x=norm(getMod()-x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x!=0);
        return power(*this,getMod()-2);
    }
    constexpr MLong &operator*=(MLong rhs)&{
        x=mul(x,rhs.x,getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs)&{
        x=norm(x+rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs)&{
        x=norm(x-rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs)&{
        return *this*=rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs,MLong rhs){
        MLong res=lhs;
        res*=rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs,MLong rhs){
        MLong res=lhs;
        res+=rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs,MLong rhs){
        MLong res=lhs;
        res-=rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs){
        MLong res=lhs;
        res/=rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is,MLong &a){
        i64 v;
        is>>v;
        a=MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os,const MLong &a){
        return os<<a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs){
        return lhs.val()==rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs){
        return lhs.val()!=rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod=i64(1E18)+9;

template<int P>
struct MInt{
    int x;
    constexpr MInt():x{}{}
    constexpr MInt(i64 x):x{norm(x % getMod())}{}
    
    static int Mod;
    constexpr static int getMod(){
        if(P>0)return P;
        else return Mod;
    }
    constexpr static void setMod(int Mod_){
        Mod=Mod_;
    }
    constexpr int norm(int x)const{
        if(x<0)x+=getMod();
        if(x>=getMod())x-=getMod();
        return x;
    }
    constexpr int val()const{
        return x;
    }
    explicit constexpr operator int() const{
        return x;
    }
    constexpr MInt operator-() const{
        MInt res;
        res.x=norm(getMod()-x);
        return res;
    }
    constexpr MInt inv() const{
        assert(x!=0);
        return power(*this,getMod()-2);
    }
    constexpr MInt &operator*=(MInt rhs)&{
        x=1LL*x*rhs.x%getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs)&{
        x=norm(x+rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs)&{
        x=norm(x-rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs)&{
        return *this*=rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs,MInt rhs){
        MInt res=lhs;
        res*=rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs,MInt rhs){
        MInt res=lhs;
        res+=rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs,MInt rhs){
        MInt res=lhs;
        res-=rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs,MInt rhs){
        MInt res=lhs;
        res/=rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is,MInt &a){
        i64 v;
        is>>v;
        a=MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os,const MInt &a){
        return os<<a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs){
        return lhs.val()==rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs){
        return lhs.val()!=rhs.val();
    }
};

template<>
int MInt<0>::Mod=998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P=998244353;
using Z=MLong<P>;
struct Comb{
    int n;
    vector<Z> _fac,_inv;
 
    Comb():_fac{1},_inv{0}{}
    Comb(int n):Comb(){init(n);}
    void init(int m){
        if(m<=n)return;
        _fac.resize(m+1);_inv.resize(m+1);
        for(int i=n+1;i<=m;i++)_fac[i]=_fac[i-1]*i;
        _inv[m]=_fac[m].inv();
        for(int i=m;i>n;i--)_inv[i-1]=_inv[i]*i;
        n=m;
    }
    Z fac(int x){
        if(x>n)init(x);
        return _fac[x];
    }
    Z inv(int x){
        if(x>n)init(x);
        return _inv[x];
    }
    Z C(int x,int y) {
        if(x<0||y<0||x<y)return 0;
        return fac(x)*inv(y)*inv(x-y);
    }
    Z P(int x,int y) {
        if(x<0||y<0||x<y)return 0;
        return fac(x)*inv(x-y);
    }
}comb(1<<21);
void solve(){
	int n;std::cin>>n;
	std::vector<int> a(n+1);
	for(int i=1;i<=n;i++)std::cin>>a[i];
	std::map<int,Z> f[2][2][2];
	int cur=0;
	f[cur][1][1][a[1]-1]=1;
	auto op=[&](int l,int r,int cnt,Z res){
		auto it=f[cur^1][l][r].find(cnt);
		if(it==f[cur^1][l][r].end())f[cur^1][l][r][cnt]=res;
		else f[cur^1][l][r][cnt]+=res;
	};
	for(int i=1;i<n;i++){
		for(int l=0;l<2;l++){
			for(int r=0;r<2;r++)f[cur^1][l][r].clear();
		}
		for(int l=0;l<2;l++){
			for(int r=0;r<2;r++){
				for(auto [cnt,res]:f[cur][l][r]){
					if(cnt==0&&l==0&&r==0)continue;
					if(cnt>0&&cnt<=a[i+1]){
						op(0,0,a[i+1]-cnt,res*comb.C(a[i+1]-1,cnt-1));
					}
					if(l==1&&cnt<=a[i+1]-1){
						op(1,0,a[i+1]-cnt-1,res*comb.C(a[i+1]-1,cnt));
					}
					if(r==1&&cnt<=a[i+1]-1){
						op(0,1,a[i+1]-cnt-1,res*comb.C(a[i+1]-1,cnt));
					}
					if(l==1&&r==1&&cnt<=a[i+1]-2){
						op(1,1,a[i+1]-cnt-2,res*comb.C(a[i+1]-1,cnt+1));
					}
				}
			}
		}
		cur^=1;
	}
	Z ans=0;
	for(int l=0;l<2;l++){
		for(int r=0;r<2;r++){
			ans+=f[cur][l][r][0];
		}
	}
	std::cout<<ans<<'\n';

}
signed main(){
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	std::cout<<std::fixed<<std::setprecision(10);
	int T=1;
	//std::cin>>T;
	while(T--)solve();
	return 0;
}