Luogu6049 燔祭

题意:一棵带点权有标号有根树 满足:

  • 每个点的点权都在

  • 父亲的点权大于等于儿子

为广义有标号堆。求有 个节点的广义有标号堆数目。

答案对 取模,,时限


方案数有显然上界 ,这提示我们答案是关于 次多项式。可以用简单 DP 配合归纳法证明。

个点的树根点权为 的方案数,求出 后插值即可。

考虑一个根权值为 的树是怎么造出来的:选若干根权值 的树(无序集合),连向根。

根据 SET 变换,,则有递推式 考虑如何进行一次递推,等价于:给出 ,有 ,求

的递推是熟知的,于是可以 得到

边界:,即有标号有根树。

总复杂度 。若使用 NTT 可以做到