题解：P11539 [Code+#5] 方案计数

· · 题解

结论：建立析合树，若存在析点，答案为 0，否则答案为 \prod \mathrm{Catalan}(|son_u|-1)。

首先将题意稍微转化一下，先确定每一层的划分，然后每次的 rand_int(0,1) 就不用管了，显然能生成 P 的方案唯一。

然后将点重新标号一下，从 [1,n] 上划分出 P 变成 P 中划分出 [1,n]，显然答案不变。

对于 P 已经排好序的情况，每一次的划分都没有限制，设 f_i 表示长度为 i 的序列的划分方案，枚举第一次划分有：

f_i=\sum_{j=1}^{i-1}f_jf_{i-j}

这就是经典的卡特兰数，所以 f_i = \mathrm{Catalan}(i-1)。

然后考虑暴力的算法，如果直接仿照上面的 DP，时间复杂度会达到 O(n^3)。

转而考虑原序列的本原连续段，一个连续段的定义是 [l,r] 表示在 p_l,\dots,p_r 内值域是一个连续的区间，而本原连续段就是不存在与之相交却无包含关系的连续段的连续段。

取出所有这样的连续段，将其建成一棵树，这个树即析合树。

现在，我们首先说明存在析点（儿子序列的任意子区间都不是连续段）就无解。

对于这一次划分，首先不能从一个儿子的区间中分开，否则就和本原连续段的定义矛盾。因为析点的性质，导致其不存在任意一个合法的划分，答案即为 0。

然后对于一个合点（儿子是正序或者逆序），同样的不能从一个儿子的区间中分开，把这些段看成一个点，那么就是首先任意建立这些点的二叉树，最后再从每个点递归下去。

于是答案是卡特兰数之积的形式也比较显然了。