P5430

· · 题解

虽然 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)。