ARC104F Visibility Sequence

大概有两种做法。

首先写一下官方题解的做法。

我们设 iPii \to P_i 存在一条边,同时将 Pi=1P_i=-1 看做 Pi=0P_i = 0 ,并添加虚点 00 ,于是对于任意一个排列,必然可以对应成为一棵树的形态。也就是说现在我们只需要统计这种树的种类数即可。

然后会发现,对于整棵树的一个子树,它必然在序列上对应一个区间,而它的根就是区间的左端点。考虑任意一个位置 ii ,它后面的第一个比它大的位置在 jj ,考虑 [i+1,j1][i+1,j-1] 这一段之间的所有数,显然它们不会连到 ii 的前面。再考虑 jj 向后的位置,它们不可能连到 jj 前面,因此 ii 的子树一定是这么一段区间。

考虑一棵子树,在删除根后它的儿子的子树就会构成一个森林。设子树从左到右的权值分别是 A1,A2,,AkA_1,A_2,\dots ,A_k ,当前位置的权值是 AA ,那么必然有

A>max{A1,A2,,Ak}A1A2AkA > \max\{A_1,A_2,\dots ,A_k\}\\ A_1 \le A_2 \le \cdots \le A_k

因为如果这个位置 \le 后面某个位置的权值,那么那个位置会成为这个位置的兄弟。而这些子树的权值如果不满足大小关系,内部就不是兄弟关系而是父子关系了。

显然,我们考虑所有点的权值都尽量小的时候一种树的形态是否存在,而且这样的话同一种树的形态必然对应唯一一种权值序列。

于是可以考虑设 f[x][l][r]f[x][l][r] 表示区间 [l,r][l,r] 构成了一棵树,根为 ll最小情况下权值是 xx ,设 g[x][l][r]g[x][l][r] 表示区间 [l,r][l,r] 构成了一个森林,森林最右边的树的根最小情况下的值为 xx 的方案数量。显然这种情况下权值不需要超过 nn ,于是可以直接给每个点的上限与 nn 取较小值。

考虑转移。

所以树的转移很简单

f[x][l][r]=g[x1][l+1][r]f[x][l][r] = g[x-1][l + 1][r]

考虑森林的转移,这种转移的常见操作是枚举一棵树,然后分成一棵树和剩下的森林,这里显然枚举后面的树会比较方便。由于 g[x][l][r]g[x][l][r] 表示的是权值最小的情况下最右边的子树权值是 xx 的森林个数,所以转移的时候,需要满足两边必须有一边的最小情况下的的权值是 xx 。如果是左边满足,那么直接把右边的子树的根的权值变成 xx ,如果右边满足就没必要修改。

g[x][l][r]=f[x][l][r]+max(a,b)=xp=lr1f[a][l][r]×g[b][l][r]g[x][l][r] = f[x][l][r] + \sum_{\max(a,b) = x} \sum_{p=l}^{r-1} f[a][l][r]\times g[b][l][r]

这样就可以不重不漏计算了,复杂度是 O(n4)O(n^4)一份代码

还有一种 zjk 做法(非常好写)。

类似刚刚的思路,考虑所有点的权值都尽量小的情况下,会发现一棵原题中的树会对应唯一一种笛卡尔树。因为会发现原题中的树进行一次左兄弟,右儿子的变化后就会成为一棵笛卡尔树!不难发现做完这个操作后,这个笛卡尔树必须满足左儿子和当前点可以相等,而右儿子必须小于。

一张看起来非常阳间的配图:

image.png
#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();
}
\