# 知识点: 拉格朗日插值

## 题意简述

$$S_k(n) = \sum_{i=1}^{n}i^k$$

$1\le n\le 10^9,\ 1\le k\le 10^6$。

## 分析题意

### 一个性质

$S_k(n)$ 为关于 $n$ 的 $k+1$ 次多项式。

\begin{aligned} &(i+1)^{d+1} - i^{d+1}\\ = &\sum_{j=0}^{d+1}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j - i^{d+1}\\ = &\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j \end{aligned}

\begin{aligned}&\sum_{i=1}^{n}\left\{(i+1)^{d+1} - i^{d+1}\right\}\\=&\sum_{i=1}^{n}\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j\end{aligned}

\begin{aligned}&\sum_{i=1}^{n}\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)i^j\\=&\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)\sum_{i=1}^{n}i^j\\=&\sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)\end{aligned}

$$(n+1)^{d+1} - 1 = \sum_{j=0}^{d}\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)$$

$$\left(\begin{matrix}d+1\\d\end{matrix}\right)S_d(n) = (n+1)^{d+1} -\sum_{j=0}^{d-1}\left\{\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)\right\} - 1$$

$$S_d(n) = \dfrac{1}{d+1}\left\{\sum_{j=0}^{d+1}n^j -\sum_{j=0}^{d-1}\left\{\left(\begin{matrix}d+1\\j\end{matrix}\right)S_j(n)\right\} - 1\right\}$$

### 具体实现

$$S_k(n)= \sum_{i=1}^{k+2}S_k(i)\prod_{i\not ={j}}\dfrac{n-j}{i-j}$$

$$S_k(n)= \sum_{i=1}^{k+2}S_k(i)\dfrac{\prod\limits_{i\not ={j}}{(n-j)}}{\prod\limits_{i\not ={j}}(i-j)}$$

\begin{aligned} &\dfrac{1}{\prod\limits_{i\not ={j}}(i-j)}\\ = &\dfrac{1}{i(i-1)(i-2) \dots 1 \times(-1) \dots (k+2-i-1)(k+2-i)}\\=&(-1)^{k+2-i}\dfrac{1}{i! (k+2-i)!} \end{aligned}

\begin{aligned} &\prod\limits_{i\not ={j}}{(n-j)}\\ =& n(n-1) \dots (n-(i-1))(n-(i+1))\dots (n-(k+2))\\ =&(\prod_{j=1}^{i-1}(n-j)) (\prod_{j=i+1}^{k+2}(n-j))& \end{aligned}

$$S_k(n)= \sum_{i=1}^{k+2}(-1)^{k+2-i}S_k(i)\dfrac{(\prod\limits_{j=1}^{i-1}(n-j)) (\prod\limits_{j=i+1}^{k+2}(n-j))}{i! (k+2-i)!}$$

### 复杂度

$O(k \log k)$ 处理 $k+2$ 个连续点值。$O(n)$ 预处理前/后 缀积，阶乘。

## 代码实现

//知识点：拉格朗日插值
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#define ll long long
const int MARX = 1e6 + 10;
const ll mod = 1e9 + 7;
//=============================================================
ll N, K, tmp, ans, pre[MARX], suf[MARX], fac[MARX];
//=============================================================
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
ll qpow(ll x, ll y, ll Mod) {
ll ret = 1;
for (; y; x = x * x % Mod, y >>= 1)
if (y & 1) ret = ret * x % Mod;
return ret;
}
//=============================================================
int main() {
pre[0] = suf[K + 3] = fac[0] = 1;
for (ll i = 1; i <= K + 2; i++) pre[i] = pre[i - 1] * (N - i) % mod;
for (ll i = K + 2; i >= 1; i--) suf[i] = suf[i + 1] * (N - i) % mod;
for (ll i = 1; i <= K + 2; i++) fac[i] = fac[i - 1] * i % mod;

for (int i = 1; i <= K + 2; i++) {
tmp = (tmp + qpow(i, K, mod)) % mod;
ll a = pre[i - 1] * suf[i + 1] % mod;
ll b = fac[i - 1] * ((K - i) & 1 ? -1 : 1) * fac[K + 2 - i] % mod;
ans = (ans + tmp * a % mod * qpow(b, mod - 2, mod) % mod) % mod;
}
printf("%lld\n", (ans + mod) % mod);
return 0;
}