自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:10:40，当前版本为作者最后更新于2021-08-09 16:55:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

虽然 EI 已经发了讲稿但我还是稍微写写。

首先考虑贡献其实有方便的组合意义做法，当然也可以上手来一把大力解递推。
前者主要就是将「他之前所有人带来的礼物个数」重新定义为选择他之前的某个人的礼物个数进行复制，这样 $i^k$ 对 $n$ 的贡献就是在这中间跨越了一个子集的方案数，即 $2^{n-i-1}$ $(i < n)$。

因此问题变为

$$n^k + \sum\limits_{i=1}^{n-1} i^k 2^{n-i-1}$$

我们不妨直接考虑形如

$$\sum\limits_{i=0}^{n-1} i^k q^i$$

的问题。显然其为

$$\left[\frac{z^k}{k!}\right] \sum\limits_{i=0}^{n-1} q^i \mathrm e^{iz} = \left[\frac{z^k}{k!}\right] \frac{1-(q\mathrm e^z)^n}{1-q\mathrm e^z} $$

令 $F(z) = \frac{1-(qz)^n}{1-qz},P(z)=1-(qz)^n$，考虑

$$F(z+1) = \frac{P(z+1)}{(1-q)-qz}$$

考虑其有递推

$$(1-q)F(z+1) = P(z+1) + qz F(z+1)$$

且 $P(z+1)$ 有 ODE

$$(z+1)P'(z+1) = -nP(z+1)-n$$

不妨设 $\mathscr F(z+1) = F(z+1) \bmod z^{k+1},\mathscr P(z+1) = P(z-1) \bmod z^{k+1}$，那么可以预见到

$$(1-q)\mathscr F(z+1) = \mathscr P(z+1) + qz \mathscr F(z+1) - qz^{k+1} [z^k] \mathscr F(z+1) $$

且有

$$\mathscr P'(z+1) = -z\mathscr P'(z+1) + n\mathscr P(z+1) + n - (n-k)z^{k+1} [z^k] \mathscr P(z+1) $$

根据 EI 给出的证明，可知 $[z^k] F(\mathrm e^z) = [z^k] \mathscr F(\mathrm e^z)$，而根据如上方程我们可以 $\Theta(k)$ 递推出 $\mathscr F(z)$ 各项系数，从而

$$\begin{aligned} \left[\frac{z^k}{k!}\right] \mathscr F(\mathrm e^z) &= \left[\frac{z^k}{k!}\right] \sum\limits_{i=0}^k \mathrm e^{iz} [z^i]\mathscr F(z) \\ &= \sum\limits_{i=0}^k i^k [z^i]\mathscr F(z) \end{aligned} $$

通过线性筛计算 $k$ 次幂，时间复杂度 $\Theta(k)$。