CF932E

· · 题解

看到某 lmpp 在群里说了这道题，立刻跑过来看一眼。
这不就 Binomial Sum 吗？

考察

\begin{aligned} \sum\limits_{i=0}^n \binom ni i^k &= \left[\frac{z^k}{k!}\right] \sum\limits_{i=0}^n \binom ni \mathrm e^{iz} \\ &= \left[\frac{z^k}{k!}\right] (1 + \mathrm e^z)^n \end{aligned}

注意

\left[\frac{z^k}{k!}\right] \mathrm e^{iz} = i^k

则令 F(z) = (1+z)^n，其满足 ODE

(1+z)F'(z)-nF(z) = 0

令 \mathscr F(z+1) = F(z+1) \bmod z^{k+1}，注意

(2+z)F'(z+1) - nF(z+1) = 0

手算一下可知

(2+z)\mathscr F'(z+1) - n\mathscr F(z+1) = (k-n)\binom nk z^k 2^{n-k}

提取系数，可以递推。

通过 EI 科技 可知 \left[\frac{z^k}{k!}\right] F(\mathrm e^z) = \left[\frac{z^k}{k!}\right] \mathscr F(\mathrm e^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)。