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}$
参考代码
参考代码很丑改完再放上来
