题面
先考虑如何判定，大致有两种思路，从小到大或从大到小枚举 \(i\in[1,n]\)，看每个区间 \([i,i+n-1]\) 合不合法，如果我们从小到大枚举，每次区间 \([i,i+n-1]\to [i+1,i+n]\)
时，前缀最大值位置集合的变化如下（蓝色为本来区间前缀最大值集合就有的，红色为新加入的，黄色为可能新加入的）：
然后我们考虑从大到小枚举，每次区间 \([i+1,i+n]\to [i,i+n-1]\)
时，前缀最大值集合变化如下：
这样感受一下，发现从前向后扫每次删去一个点，加入一些位置（之后可能删除）；从后向前每次加入一个点，删去一些位置（不会再次加入）。那么显然从后向前做更加简单，于是我们考虑从后向前考虑这个问题。
我们继续考虑如何判定：每次只会加入一个点，于是应该有 \(1\le x_i\le x_{i+1}+1\)
，这应当是一个必要不充分条件。然后看看删去了哪些点，他会删去最后的点和原来集合一段前缀的点。
没什么头绪，看看在满足 \(1\le x_i\le x_{i+1}+1\) 时什么时候不合法，大概是这样的情况：\(x_i=x_{i+1}+1\)，同时区间不够长了，必须删去最后一个点。于是这样两个条件无法同时满足就不合法了，同时我们注意到因为超出区间而被删去的点只能位于 \([i+1,i+n-1]\)
这个区间。
那我们就贪心地考虑这个问题，若 \(x+i\neq x_{i+1}+1\)，那我们先把最后一个点删去防止后来区间放不下最后一个点，同时删去一些前缀点，如果这样还是会出现不合法那对于当前这个 \(x\)
序列就一定不合法。
然后初始时的 \(x_n\) 告诉我们 \([i+1,i+n-1]\) 这个区间内存在 \(x_n-1\) 个前缀最大值，贪心过程中维护 \([i+1,i+n-1]\) 区间内的没被删除的点的数量以及区间内被删除的点有多少不是因为在最后位置被删去（即数量为作为前缀被删去的数量加上没被删去的数量）用于在 \(x_i=x_{i+1}+1\) 的时候判定有没有点在最后需要被删去导致不合法。 这里给出爆搜枚举 \(x\) 然后贪心判定的代码。 接着让我们开始计数吧，我们注意到贪心时对于一个位置我们只需要用到上一位和当前位选的 \(x\) 大小，以及区间 \([i+1,i+n-1]\) 中没被删去的数量 \(\text{lst}\) 和不是在最后位置被弹出的数量 \(\text{pp}\) 。 那么我们设 \(f_{i,j,k,x}\) 表示针对区间 \([i,n]\)，\(x_i=j\)，\(k,x\) 分别代表上文的 \(\text{lst}\) 和 \(\text{pp}\) 大小时合法方案总数，转移方式和贪心类似，需要枚举下一位选的什么，于是时间复杂度为 \(\Theta(n^5)\)，滚动数组一下空间复杂度就是 \(\Theta(n^3)\) 。#include
using namespace std;const int N=55;int n,a[N],x[N],ans;bool check(){int lst=x[n]-1,pp=x[n]-1;for(int i=n-1;i>=1;i--){if(x[i]>x[i+1]+1)return false;if(x[i]==x[i+1]+1){if(lst&&pp>=i)return false;continue;}int del=x[i+1]-x[i]+1,dlt=0;if(lst>0){pp--;lst--;del--;dlt++;}if(x[i+1]-lst-dlt>=del)continue;lst-=del-(x[i+1]-lst-dlt);}return true;
}void dfs(int u){if(u>n){if(check())++ans;return;}for(int i=1;i<=a[u];i++){x[u]=i;dfs(u+1);}return;
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dfs(1);cout<#include
using namespace std;const int N=55,mod=998244353;int n,a[N],f[N][N][N],g[N][N][N];int DP(){for(int i=1;i<=a[n];i++)f[i][i-1][i-1]=1;for(int i=n-1;i>=1;i--){for(int j=1;j<=a[i+1];j++)for(int k=0;k=i)continue;g[y][k][x]=(g[y][k][x]+f[j][k][x])%mod;continue;}int del=j-y+1;int nxtk=k,nxtx=x,dlt=0;if(nxtk){nxtk--;nxtx--;del--;dlt++;}if(del-(j-dlt-nxtk)>0)nxtk-=del-(j-dlt-nxtk);g[y][nxtk][nxtx]=(g[y][nxtk][nxtx]+f[j][k][x])%mod;}}for(int j=0;j<=n;j++)for(int k=0;k>n;for(int i=1;i<=n;i++)cin>>a[i];cout<