ABC252G Pre-Order 做题记录

给定一个 $n$ 的排列 $p$，求 $n$ 个节点的有标号有根树的个数，满足这棵树的先序遍历结果是 $p$。先序遍历定义如下：对于 $u$ 的子树，先输出 $u$，然后按照编号从小到大遍历 $u$ 的孩子。答案对 $998244353$ 取模，$1\le n\le 500$。

赛时开题开错顺序了，应该先做这道题再做 F 的……

可以设 $dp_{l,r}$ 表示 $[l,r]$ 构成一棵树的方案数，$pd_{l,r}$ 表示 $[l,r]$ 构成森林的方案数，那么森林可以通过森林加一棵树来转移，树可以通过一个点下面连森林来转移。

初始状态是 $dp_{l,l}=1$，$pd_{l,l}=1$，$pd_{l+1,l}=1$。前两个很好理解，最后一个则是因为森林可以为空，方便森林包含树的情况。

转移如下：

$dp_{l,r}=pd_{l+1,r}$

$pd_{l,r}=\sum\limits_{k=l}^r [p_l<p_{k+1}\lor k=r]\times dp_{l,k}\times pd_{k+1,r}$

最后答案即为 $dp_{l,r}$。