AT_abc222_h [ABC222H] Beautiful Binary Tree 题解
eastcloud
·
·
题解
首先考虑一棵树合法的充要条件，首先根节点必须是 1，因为最多只能有 n-1 次操作，每次操作必须合并两个正权值的节点，否则不合法，其次是不能有两个相邻的 0，否则子树内会存在点必须跳超过一步也不合法。
不难发现这就是充要条件，因为你总能让满足一个上面情况的树的最深的叶子往上跳到一个不为 0 的点处，然后就可以递归了。
接着是计数，考虑设出 F(x) 表示根节点为 1 的满足条件的树的生成函数，G(x) 则是根节点可以是 0，企鹅他条件必须满足的生成函数，不难得到：
F(x)=x(F(x)+G(x))^2+1,G(x)=F(x)^2-1
把 G(x) 代入就有
F(x)=x(F(x)^2+F(x)-1)^2+1
设 C(x)=F(x)-1，便于我们拉反，就能得到 C(x)=x(C(x)^2+3C(x)+1)^2，即复合逆为 \frac{x}{(x^2+3x+1)^2}。
直接扩展拉反，有：
\begin{align*}
[x^n]C(x)&=\frac{1}{n} [x^{n-1}] (x^2+3x+1)^{2n}\\
&=\sum_{i=0}\binom{2n}{i}\binom{2n-i}{n-1-2i}3^{n-1-2i}
\end{align*}
于是就做完了。