自动搬运

查看原文

来自洛谷，原作者为

	Weng_Weijie やー！今日もパンがうまい！

搬运于2025-08-24 22:07:48，当前版本为作者最后更新于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+多项式求逆 做完了