BZOJ 3864 题解

Description

n 个叶子,每个非叶节点儿子数 \in D 的有根树个数(儿子有序)。

Solution

答案的母函数:

F(x) = 1+\sum_{d\in D} F^d(x)

那么

F(x)-\sum_{d\in D}F^d(x) = 1

A(x) = x-\sum_{d\in D}x^d

则有

A(F(x)) = 1

拉格朗日反演得到

[x^n]F(x) = \frac{1}{n}[x^{-1}]\frac{1}{A^n(x)}\
= \frac{1}{n}[x^{n-1}]\left(\frac{x}{A(x)}\right)^n

其中 A(x)​ 约掉上面的 x​ 之后常数项为 1​,可以直接 ln​ + exp​

发表评论

电子邮件地址不会被公开。 必填项已用*标注