CF755G PolandBall and Many Other Balls 做题记录

有一排 $n$ 个球，定义一个组可以只包含一个球或者包含两个相邻的球。现在一个球只能分到一个组中，求从这些球中取出 $k$ 组的方案数。

$n\le 10^9$，$k<2^{15}$。

$dp_{n,k}=dp_{n-1,k}+dp_{n-1,k-1}+dp_{n-2,k-1}$

$dp_{a+b,k}=\left(\sum\limits_{i=0}^k dp_{a,i}dp_{b,k-i}\right)+\left(\sum\limits_{i=0}^{k-1}dp_{a-1,i}+dp_{b-1,k-1-i}\right)$

设 $F_n(x)\sum\limits_{k=0}^{\inf}x^kdp_{n,k}$，那么：

$F_n(x)=F_{n-1}(x)+xF_{n-1}(x)+xF_{n-2}(x)$

$F_{a+b}(x)=(F_a*F_b)(x)+x(F_{a-1}*F_{b-1})(x)$

那么：

$F_n(x)=F_{n-1}(x)+xF_{n-1}(x)+xF_{n-2}(x)$

$F_{2n}(x)=F_n^2(x)+xF_{n-1}^2(x)$

$F_{2n-1}(x)=(F_n*F_{n-1})(x)+x(F_{n-1}*F_{n-2})(x)$

$F_{2n-2}(x)=F_{n-1}^2(x)+xF_{n-2}^2(x)$