BZOJ3157: 国王奇遇记 & 3516: 国王奇遇记加强版

令\[S_i=\sum_{k=1}^n k^i m^k\]我们有\[\begin{eqnarray*}(m-1)S_i & = & mS_i - S_i \& = & \sum_{k=1}^n k^i m^{k+1} - \sum_{k=1}^n k^i m^k \& = & \sum_{k=2}^{n+1} (k-1)^i m^k - \sum_{k=1}^n k^i m^k \& = & n^i m^{n+1} + \sum_{k=1}^n m^k\big( (k-1)^i - k^i\big) \& = & n^i m^{n+1} + \sum_{k=1}^n \bigg( \sum_{j=1}^{i-1} (-1)^{i-j}{i \choose j}k^j m^k \bigg) \& = & n^i m^{n+1} + \sum_{j=0}^{i-1} (-1)^{i-j}{i \choose j} S_j\end{eqnarray*}\]直接按照这条式子\(O(m^2)\)递推即可。令\[S_i=\sum_{k=1}^n k^i m^k\]我们有\[\begin{eqnarr