考虑把式子化简：

$\sum\limits_{i=0}^n {n\choose i}i^k=\sum\limits_{i=1}^n{n\choose i}\sum\limits_{j=1}^k\begin{Bmatrix} k\\ j\end{Bmatrix}\frac{i!}{(i-j)!}$

考虑把阶乘处理掉，因为太丑了：

$\sum\limits_{i=0}^n{n\choose i}i^k=\sum\limits_{j=1}^k \begin{Bmatrix} k\\ j\end{Bmatrix}j!\sum\limits_{i=0}^n {n\choose i}{i\choose j}$

把组合数结合一下然后化简：

$\sum\limits_{i=0}^n {n\choose i}i^k=\sum\limits_{j=1}^k \begin{Bmatrix}k\\ j\end{Bmatrix}j!\sum\limits_{i=0}^n{n\choose j}{n-i\choose n- j}$

把 $\sum\limits_{i=0}^n {n-i\choose n-j}$ 看作 ${n\choose j}$ 的系数，然后将 $i$ 整体修改得到：

$\sum\limits_{i=0}^n {n\choose i}i^k=\sum\limits_{j=1}^k\begin{Bmatrix}k\\ j\end{Bmatrix}j!{n\choose j}\sum\limits_{i=0}^{n-j} {n-i\choose i}$

最后根据组合数的性质，化简出：

$\sum\limits_{i=0}^n {n\choose i}i^k=\sum\limits_{j=1}^k \begin{Bmatrix}k\\ j\end{Bmatrix}j!{n\choose j}2^{n-j}$

虽然是垃圾的 $O(k\log n)$，但是你就说能不能过吧。