考虑把式子化简:

i=0n(ni)ik=i=1n(ni)j=1k{kj}i!(ij)!\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}\dfrac{i!}{(i-j)!}

考虑把阶乘处理掉,因为太丑了:

i=0n(ni)ik=j=1k{kj}j!i=0n(ni)(ij)\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}

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

i=0n(ni)ik=j=1k{kj}j!i=0n(nj)(ninj)\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}

i=0n(ninj)\sum\limits_{i=0}^n {n-i\choose n-j} 看作 (nj){n\choose j} 的系数,然后将 ii 整体修改得到:

i=0n(ni)ik=j=1k{kj}j!(nj)i=0nj(nii)\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}

最后根据组合数的性质,化简出:

i=0n(ni)ik=j=1k{kj}j!(nj)2nj\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(klogn)O(k\log n),但是你就说能不能过吧。