题解 P5162 【WD与积木】

Weng_Weijie · 2019-01-26 13:19:40 · 题解

由于是选出积木有标号，所以使用指数型生成函数

先考虑选的方案数

显然每一层的生成函数为 F(x)=\displaystyle\sum_{k=1}^{\infty}\dfrac 1{k!}x^k=e^x-1

枚举层数，答案即为 \displaystyle\sum_{k=0}^{\infty}F^k(x)=\dfrac 1{1-F(x)}=\dfrac 1{2-e^x}

接下来求所有方案的层数总和

枚举层数，答案即为 \displaystyle\sum_{k=0}^{\infty}kF^k(x)=\dfrac {F(x)}{(1-F(x))^2}=\dfrac{e^x-1}{(2-e^x)^2}

然后就可以用 FFT+多项式求逆 做完了