2021牛客暑期多校训练营4

G. Product

题目链接

解题思路

我们可以通过卷积的思路思考

先不考虑$k$,多项式$(\sum_{i=1}^D\frac{1}{i!}x^i)^n$的$x^D$的系数即为$\sum_{a_i\ge0,\sum_{a_i}=D}\prod _i\frac{1}{a_i!}$

考虑到$e^x$​​在$0$​​点的泰勒展开,所以$\sum_{a_i\ge0,\sum_{a_i}=D}\prod i\frac{1}{a_i!}$​​就等于$(e^x)^n=e^{xn}$​​在0点的泰勒展开的第$x^D$​​相的系数。所以我们得到:
$$\sum{a_i\ge0,\sum_{a_i}=D}\prod_i\frac{1}{a_i!}=\frac{n^D}{D!}$$
题目等价于求:
$$\begin{align}
&D!\sum_{a_i\ge0,\sum_{a_i}=D}\prod_i^n\frac{1}{(a_i+k)!}\\
=&D!\sum_{a_i\ge k,\sum_{a_i}=D+nk}\prod_i^n\frac{1}{a_i!}
\end{align}$$

我们可以枚举$a_i$中小于$k$的个数和这些$a_i$的和,然后通过容斥的到
$$\begin{align}
&D!\sum_{a_i\ge0,\sum_{a_i}=D}\prod_i^n\frac{1}{(a_i+k)!}\\
=&D!\sum_{a_i\ge k,\sum_{a_i}=D+nk}\prod_i^n\frac{1}{a_i!}\\
=&D!\sum_{x=0}^{n}\sum_{y=0}^{nk}\textrm{C}n^x(-1)^x\frac{(n-x)^{D+nk-y}}{(D+nk-y)!}\mathrm{dp}(x,y)\\
=&\sum_{x=0}^{n}\sum_{y=0}^{nk}(-1)^x\textrm{C}n^x(n-x)^{D+nk-y}\mathrm{dp}(x,y)\frac{D!}{(D+nk-y)!}
\end{align}$$
其中

$\mathrm{dp}(x,y)=\sum{0\le a<k,\sum_{a_i}=y}\prod_{i=1}^n\frac{1}{a_i!}=\sum_{i=0}^{k-1}\left [\frac{1}{i!}\times \mathrm{dp}(x-1,y-i)\right ]$​​​​

特别的$\mathrm{dp}(0,0)=1$

时间复杂度为$O((nk)^2)$​,时间复杂度上限取决于计算$\mathrm{dp}$​

参考代码

参考代码很丑改完再放上来
EricXia

EricXia

喜欢睡觉,热爱钻研各种问题。