给定一个 n 的排列 p,求 n 个节点的有标号有根树的个数,满足这棵树的先序遍历结果是 p。先序遍历定义如下:对于 u 的子树,先输出 u,然后按照编号从小到大遍历 u 的孩子。答案对 998244353 取模,1≤n≤500。
赛时开题开错顺序了,应该先做这道题再做 F 的……
可以设 dpl,r 表示 [l,r] 构成一棵树的方案数,pdl,r 表示 [l,r] 构成森林的方案数,那么森林可以通过森林加一棵树来转移,树可以通过一个点下面连森林来转移。
初始状态是 dpl,l=1,pdl,l=1,pdl+1,l=1。前两个很好理解,最后一个则是因为森林可以为空,方便森林包含树的情况。
转移如下:
dpl,r=pdl+1,r
pdl,r=k=l∑r[pl<pk+1∨k=r]×dpl,k×pdk+1,r
最后答案即为 dpl,r。