题意

给定 $n,k$ ，求

$$\sum_{i=1}^ni^k $$

对 $10^9+7$ 取模的值。

$n\leq10^{18},k\leq5\times10^4$ 。

口胡

多项式做少了就想不到多项式。

首先令 $F(x)=\sum_{i=1}^xi^k$ ，然后它是 $k+1$ 次的多项式。那么可以先求出前 $k+2$ 项，然后拉插求出 $F(n)$ 。

题解

MD 原来以前做过。

$x_i=i,y_i=F(i)$ 。将这个代入拉格朗日插值公式：

$$F(n)=\sum_{i=1}^{k+2}F(i)\prod_{j\neq i}\frac{n-j}{i-j}\quad(n>k+2) $$

然后要把这个式子化一下：

$$\begin{aligned}F(n)&=\sum_{i=1}^{k+2}F(i)\frac{\left(\frac{\prod\limits_{j=n-k-1}^{n-1}j}{n-i}\right)}{(i-1)!(k+2-i)!}\cdot(-1)^{k+2-i}\\&=\left(\prod\limits_{j=n-k-1}^{n-1}j\right)\sum_{i=1}^{k+2}F(i)\frac{(-1)^{k+2-i}}{(i-1)!(k+2-i)!(n-i)}\end{aligned} $$

所以在 $n>k+2$ 时就 $\mathcal{O}(k\log p)$ 解决了，其中 $p$ 是模数。当 $n\leq k+2$ 时，由于 $k\leq 10^6$ ，就直接 $\mathcal{O}(n)$ 解决。

代码：

ll fac[M], res, sum, ans, mod = 1e9 + 7;
int n, k;

ll qpow(ll a, int b) {
	ll ans = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) ans = ans * a % mod;
	return ans;
}

int main() {
	scanf ("%d%d", &n, &k);
	if (n <= M) {
		for (int i = 1; i <= n; i++)
			ans = (ans + qpow(i, k)) % mod;
		printf ("%lld\n", ans);
		return 0;
	}
	fac[0] = res = 1;
	for (int i = 1; i <= k + 2; i++) {
		res = res * (n - i) % mod; 
		fac[i] = fac[i - 1] * i % mod;
	}
	for (int i = 1; i <= k + 2; i++) {
		sum = (sum + qpow(i, k)) % mod;
		ll val = sum * qpow(fac[i - 1] * fac[k + 2 - i] % mod * (n - i) % mod, mod - 2);
		ans = (ans + val * (((k + 2 - i) & 1)? -1: 1)) % mod;
	}
	printf ("%lld\n", (ans * res) % mod);
    return 0;
}