【bzoj3625】【xsy1729】小朋友和二叉树 - 生成函数+FFT

OI

---

题意

给定$n$，给定$c_1,c_2,...,c_m$。
给定$m$，对于任意$s\leq m$，求每个点权属于$c$，权值和为$s$的二叉树的个数。

$1\leq n,m\leq 10^5$
答案对$998244353(7*17*2^23+1,一个质数)$取模。

分析

设

$$v_k=\sum_{i=1}^n[c_i==k]$$
设$v_k$的生成函数为 $$C=\sum_{i=0}^\infty v_ix^i$$

设$f_k$表示权值和为$k$的二叉树的个数。
设$f$的生成函数为

$$F=\sum_{i=0}^\infty f_ix^i$$

当$k=0$时，

$$f_0=1$$
当$k>0$时， $$f_k=\sum_{i=0}^kc_i\sum_{j=0}^{k-i}f_jf_{k-i-j}$$
所以 $$F(x)=C(x)*F(x)*F(x)+1$$
解得： $$F(x)={1\pm \sqrt{1-4C(x)}\over 2C(x)}$$

由于我们只需要求前$m$项。
所以

$$F(x)\equiv {1\pm \sqrt{1-4C(x)}\over 2C(x)}(\mod x^m)$$

检验：
（1）当

$$F(x)\equiv {1+ \sqrt{1-4C(x)}\over 2C(x)}(\mod x^m)$$
有 $$\lim_{x\rightarrow 0}F(x)\equiv \infty(\mod x^m)$$
舍去。
（2）当 $$F(x)\equiv {1- \sqrt{1-4C(x)}\over 2C(x)}(\mod x^m)$$
有 $$\lim_{x\rightarrow 0}F(x)\equiv 1(\mod x^m)$$
所以， $$F(x)\equiv {1- \sqrt{1-4C(x)}\over 2C(x)}(\mod x^m)$$

分子分母同时乘上$1+\sqrt{1-4C(x)}$，
得到

$$F(x)={4C(x)\over 2C(x)(1+\sqrt{1-4C(x)})}={2\over 1+\sqrt{1-4C(x)}}$$
考虑多项式开根+多项式求逆，求解该问题。

多项式求逆：
http://blog.miskcoo.com/2015/05/polynomial-inverse
问题描述：已知$A(x)$，求$B(x)$，使得$A(x)B(x)\equiv 1(\mod x^m)$
解决方案：
①当$m=1$时，设$A(x)=c$，则$B(x)=inv(c)(\mod x^m)$
②当$m>1$时，设$A(x)B'(x)\equiv 1(\mod x^{m\over 2})$，现在要求$B(x)$。
$A(x)B(x)\equiv 1(\mod x^m)$
$A(x)B(x)\equiv 1(\mod x^{m\over 2})$
$B(x)-B'(x)\equiv 0(\mod x^{m\over 2})$
$B^2(x)-2BB'(x)+B'^2(x)\equiv 0(\mod x^m)$
两边同时乘上$A(x)$
$B(x)-2B'(x)+AB'^2(x)\equiv 0(\mod x^m)$
$B(x)=2B'(x)-AB'^2(x)$

多项式开根：
http://blog.csdn.net/wzq_qwq/article/details/48394749
问题描述：已知$A(x)$，求$H(x)$，满足$H^2(x)\equiv A(x)(\mod x^m)$
解决方案：
①当$m=1$时，直接求逆元
②当$m>1$时，设$G(x)$，满足$G^2(x)=A(x)(\mod x^{m\over 2})$
$(G^2(x)-A(x))^2\equiv 0(\mod x^m)$
$G^4(x)-2G^2(x)A(x)+A^2(x)\equiv 0(\mod x^m)$
$(A(x)+G^2(x))^2\equiv 4G^2(x)A(x)(\mod x^m)$
$A(x)\equiv ({A(x)+G^2(x)\over 2G(x)})^2=H^2(x)(\mod x^m)$
$H(x)={A(x)+G^2(x)\over 2G(x)}\equiv {A(x)\over 2G(x)}+{G(x)\over 2}(\mod x^m)$