ABC252G Pre-Order 做题记录

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

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

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

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

转移如下:

dpl,r=pdl+1,rdp_{l,r}=pd_{l+1,r}

pdl,r=k=lr[pl<pk+1k=r]×dpl,k×pdk+1,rpd_{l,r}=\sum\limits_{k=l}^r [p_l<p_{k+1}\lor k=r]\times dp_{l,k}\times pd_{k+1,r}

最后答案即为 dpl,rdp_{l,r}