BZOJ3625小朋友与二叉树

小朋友与二叉树

Solution

对$C$这一维做一个生成函数,易得$C(x)=\sum_{i\in S}x^i$

然后我们在考虑二叉树,对于二叉树做一个生成函数$F(x)$。

我们不难发现
$$
F(x)=C(x)F^2(x)+1
$$
为什么是这样呢?我们考虑左右儿子合并在一起之后就是$F^2(x)$再加上根自己的贡献就是$F^2(x)C(x)$,然后我们发现常数项没有了,所以最后$+1$表示空树。

然后我们就可以愉快的解方程了,通过求根公式可以得到
$$
F(x)=\frac{1\pm\sqrt{1-4C(x)}}{2C(x)}
$$
其中有一个$\pm$该怎么办呢?通过简单观察我们可以发现,分母的常数项为$0$。如果是$+$,那么开根号后得到的多项式的常数项一定是一个非负数,所以这样分子就一定会有常数项,那么整个分数就一定会有余数。故上面只能为$-$。

于是我们就可以通过之前介绍过的多项式开根和多项式求逆元解决这道题了。