题意:一棵带点权有标号有根树 满足:
称 为广义有标号堆。求有 个节点的广义有标号堆数目。
答案对 取模,,,时限 。
方案数有显然上界 ,这提示我们答案是关于 的 次多项式。可以用简单 DP
配合归纳法证明。
设 为 个点的树根点权为 的方案数,求出 后插值即可。
设 考虑一个根权值为
的树是怎么造出来的:选若干根权值 的树(无序集合),连向根。
根据 SET 变换,,则有递推式 考虑如何进行一次递推,等价于:给出 ,有 ,求 。
的递推是熟知的,于是可以 从
得到 。
边界:,即有标号有根树。
总复杂度 。若使用 NTT
可以做到 。