大概有两种做法。
首先写一下官方题解的做法。
我们设 存在一条边,同时将 看做 ,并添加虚点 ,于是对于任意一个排列,必然可以对应成为一棵树的形态。也就是说现在我们只需要统计这种树的种类数即可。
然后会发现,对于整棵树的一个子树,它必然在序列上对应一个区间,而它的根就是区间的左端点。考虑任意一个位置 ,它后面的第一个比它大的位置在 ,考虑 这一段之间的所有数,显然它们不会连到 的前面。再考虑 向后的位置,它们不可能连到 前面,因此 的子树一定是这么一段区间。
考虑一棵子树,在删除根后它的儿子的子树就会构成一个森林。设子树从左到右的权值分别是 ,当前位置的权值是 ,那么必然有
因为如果这个位置 后面某个位置的权值,那么那个位置会成为这个位置的兄弟。而这些子树的权值如果不满足大小关系,内部就不是兄弟关系而是父子关系了。
显然,我们考虑所有点的权值都尽量小的时候一种树的形态是否存在,而且这样的话同一种树的形态必然对应唯一一种权值序列。
于是可以考虑设 表示区间 构成了一棵树,根为 ,最小情况下权值是 ,设 表示区间 构成了一个森林,森林最右边的树的根最小情况下的值为 的方案数量。显然这种情况下权值不需要超过 ,于是可以直接给每个点的上限与 取较小值。
考虑转移。
所以树的转移很简单
考虑森林的转移,这种转移的常见操作是枚举一棵树,然后分成一棵树和剩下的森林,这里显然枚举后面的树会比较方便。由于 表示的是权值最小的情况下最右边的子树权值是 的森林个数,所以转移的时候,需要满足两边必须有一边的最小情况下的的权值是 。如果是左边满足,那么直接把右边的子树的根的权值变成 ,如果右边满足就没必要修改。
这样就可以不重不漏计算了,复杂度是 。一份代码 。
还有一种 zjk 做法(非常好写)。
类似刚刚的思路,考虑所有点的权值都尽量小的情况下,会发现一棵原题中的树会对应唯一一种笛卡尔树。因为会发现原题中的树进行一次左兄弟,右儿子的变化后就会成为一棵笛卡尔树!不难发现做完这个操作后,这个笛卡尔树必须满足左儿子和当前点可以相等,而右儿子必须小于。
一张看起来非常阳间的配图:

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 126
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 1e9 + 7;
int n , m;
int A[MAXN];
vi val;
int dp[MAXN][MAXN][MAXN];
int fuck( int l , int r , int x ) {
int& s = dp[l][r][x];
if( ~s ) return s;
if( l > r ) return s = 1;
if( !x ) return 0;
s = 0;
rep( p , l , r ) s = ( s + fuck( l , p - 1 , min( x , A[p] ) ) * 1ll * fuck( p + 1 , r , min( x , A[p] ) - 1 ) ) % P;
return s;
}
void solve() {
cin >> n;
rep( i , 1 , n ) scanf("%d",A + i) , A[i] = min( A[i] , n );
memset( dp , -1 , sizeof dp );
cout << fuck( 1 , n , n ) << endl;
}
signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}