求自然数幂的和 – CF622F
问题 给定 $n, k$,求出: $$ 1^k+2^k+\cdots+n^k=\sum_{i=1}^{n}{i^k}\bmod 1000000007 $$ $n\leq 10^9$,$k\leq 10^6$. 解决这个问题需要用到一些简单的多项式技巧。 拉格朗日插值 如果给定一个 $k$ 次多项式上的 $k+1$ 个点值,就可以通过拉格朗日差值求出…