题解 CF438E 【The Child and Binary Tree】

· · 题解

自己在家里乱搞了搞竟然搞出来了2333。
看到模数\text{998244353}第一反应就是多项式题。
首先可以列出一个很显然易见的式子：
设f_i表示点权和为i的符合条件的二叉树的个数，g_i表示权值i是否包含在c中

f_0=1 f_n=\sum_{i=1}^ng_i\sum_{j=1}^{n-i}f_jf_{n-i-j}[n>0]

这个式子的意思枚举一下一个权值是否存在，然后枚举一下左右子树的权值，方案数加起来就好。
不难发现这个式子就是3个多项式卷在一起。
令F表示序列f的生成函数，G表示序列G的生成函数。 那么：

F=G*F^2+1

根据小学数学中的一元二次方程求根公式，我们可以把这个式子的根求出来。

F=\frac{1± \sqrt{1-4G}}{2G}

此时发现有2解，分别讨论一下。

\text{当取正}\text{号时}\lim_{x→0}\text{为}\infty,\text{舍去} \text{当取负}\text{号时}\lim_{x→0}\text{为1},\text{满足}

故F=\frac{1-\sqrt{1-4G}}{2G}
化简一下得到

F=\frac{2}{1+\sqrt{1-4G}}

开根+求逆即可。