接下来求解前缀幂次和
求解 \(\sum_{i = 1}^{k} i^k\)
\[
\begin{aligned}
(p+1)^k - 1 = (p+1)^k - p^k + p^k - (p-1)^k + \dots + p^1 - 1 \(p+1)^k - p^k = \sum_{i=0}^{k-1} \binom{k}{i} p^i \\
(p+1)^k - 1 = \sum_{j=1}^{p} \sum_{i=0}^{k-1} \binom{k}{i} j^i = \sum_{i=0}^{k-1} \binom{k}{i} \sum_{j=1}^{p} j^i
\end{aligned}
\]
设 \(Psum(p, k) = \sum_{i = 1} ^ {p} i ^ k\) 即 \(k\) 次幂的前缀和
\[
\begin{aligned}
(p+1)^{k+1} - 1 = sum_{i=0}^{k} \binom{k+1}{i} Psum(p, i) \Psum(p, k) = \frac{ (p+1)^{k+1} - 1 - \sum_{i=0}^{k-1} \binom{k+1}{i} Psum(p, i) }{ \binom{k+1}{k} } \\end{aligned}
\]
这样就是跟 \(p\) 无关了, \(O(k ^ 2)\) 暴力推
原文：https://www.cnblogs.com/Kuonji/p/11842819.html