数学课程：题解

思路

对一个排列建立大根笛卡尔树：最大值是根，最大值左侧和右侧分别递归形成左右子树。对于值 $x$，所有包含 $x$ 的连续子数组的不同最大值，恰好是笛卡尔树上从 $x$ 到根的所有祖先值。因此，$x$ 是好数当且仅当它在笛卡尔树中的深度为 $m$。问题转化为统计恰好有 $k$ 个深度为 $m$ 的结点的排列。

设 $f(d,s,c)$ 表示当前子树根深度为 $d$、子树大小为 $s$，且整棵子树中恰有 $c$ 个结点最终位于目标深度 $m$ 的排列数。

枚举最大值在当前排列中的位置。若左侧大小为 $l$，右侧大小为 $r=s-1-l$，还要从其余 $s-1$ 个值中选择 $l$ 个放入左侧，方案数为 $\binom{s-1}{l}$。再枚举目标结点数在两棵子树间的分配即可。

做法

子任务 1 枚举所有 $n!$ 个排列，用单调栈建立笛卡尔树，统计深度为 $m$ 的结点数。

子任务 2 中 $m=1$。任何非空笛卡尔树都恰有一个根结点深度为 $1$，所以当 $k=1$ 时答案是 $n!\bmod p$，否则为零。

满分做法记忆化上述区间长度动态规划。边界如下：

• 空树只有在需要的结点数为零时贡献 $1$；
• 当当前深度已经是目标深度时，只有 $c=1$ 才合法，此时当前子树的任意排列均可，贡献 $s!$；
• 若剩余深度不足以容纳非零目标数，或 $c$ 超过该深度最多可能拥有的结点数，可以立即剪枝。

组合数用杨辉三角形预处理，因此模数 $p$ 不需要是质数。

复杂度

状态数为 $O(nmk)$，直接枚举根位置和左右目标数分配，时间复杂度上界为 $O(n^2m k^2)$；剪枝后可通过本题限制。空间复杂度为 $O(nmk)$。