拉格朗日插值
考虑这样一个问题：有 \(n + 1\) 个不同的点值 \((x_{0 \sim n} , y_{0 \sim n})\) ，求一个 \(n\) 次多项式，满足其经过上述 \(n + 1\) 个点。
一般性插值法
对于第 \(i\) 个点，考虑构造一个多项式 \(F_i(k) = \begin{cases} y_i & k = x_i \\ 0 & k \not = x_i \end{cases}\) ，则 \(G(k) = \sum_{i = 0}^n F_i(k)\) 即为所求。
考虑构造 \(F_i(k)= y_i \prod_{i \not = j} \dfrac{k - x_j}{x_i - x_j}\)
解释：不难发现，当 \(k = x_j \ (j \not = i)\) 时，分子的累乘肯定有一项为 \(0\) ；当 \(k = x_i\) 时，分子分母累乘后肯定都会被约掉。因此这个多项式是符合条件的。
于是得到：
\[G(k) = \sum_{i = 0}^n y_i \prod_{j \not = i} \dfrac{k - x_j}{x_i - x_j} \]时间复杂度 \(O(n^2)\) 。
横坐标连续时的插值方法
把 \(x_i\) 替换为 \(i\) ，新的式子即为：
\[G(k) = \sum_{i = 0}^n y_i \prod_{i \not = j} \dfrac{k - j}{i - j} \]考虑优化。不难得到分子等于：
\[\dfrac{\prod_{j = 0}^n (k - j)}{k - i} \]分母等于：
\[(-1)^{n - i} (i - 1)! (n - i)! \]于是得到：
\[G(k) = \sum_{i = 0}^n y_i \dfrac{\prod_{j = 0}^n (k - j)}{(k - i) (-1)^{n - i} (i - 1)! (n - i)!} \]inline int query(int k) {
pre[0] = 1;
for (int i = 1; i <= n; ++i)
pre[i] = 1ll * pre[i - 1] * dec(k, i) % Mod;
suf[n + 1] = 1;
for (int i = n; i; --i)
suf[i] = 1ll * suf[i + 1] * dec(k, i) % Mod;
int ans = 0;
for (int i = 1; i <= n; ++i)
ans = add(ans, 1ll * y[i] * pre[i - 1] % Mod * suf[i + 1] % Mod * sgn(n - i) % Mod * invfac[i - 1] % Mod * invfac[n - i] % Mod);
return ans;
}
重心拉格朗日插值法
观察式子：
\[G(k) = \sum_{i = 0}^n y_i \prod_{i \not = j} \dfrac{k - x_j}{x_i - x_j} \]令 \(g = \prod_{i = 0}^n (k - x_i)\) ，则：
\[G(k) = g \sum_{i = 0}^n \prod_{i \not = j} \dfrac{y_i}{(k - x_i)(x_i - x_j)} \]再令 \(t_i = \dfrac{y_i}{\prod_{j \not = i} x_i - x_j}\) ，则：
\[G(k) = g \sum_{i = 0}^n \dfrac{t_i}{k - x_i} \]这样每次新加入一个点的时候只需要计算 \(g, t_i\) 即可。
应用
给定 \(n, k\) ，求 \((\sum_{i = 1}^n i^k) \bmod 10^9 + 7\) 。
\(1 \leq n \leq 10^9, 0 \leq k \leq 10^6\)
有一个结论：\(\sum_{i = 1}^n i^k\) 是一个 \(k + 1\) 次多项式。
定义数列 \(\{a_n\}\) 的 \(p\) 阶差分数列为 \(\Delta^p f(x) = \Delta(\Delta^{p - 1}f(x))\) 。若数列 \(\{a_n\}\) 的 \(p\) 阶阶差数列是一个非 \(0\) 的常数列，那么我们称数列 \(\{a_n\}\) 为 \(p\) 阶等差数列
定理：数列 \(\{a_n\}\) 是一个 \(p\) 阶等差数列的充要条件是其通项公式是一个关于 \(n\) 的 \(p\) 次多项式
先证明其充分性，必要性的证法也是类似的。设数列的通项公式 \(f(x) = \sum_{i = 0}^n a_ix^i\) ，则其一次差分数列的通项公式为：
\[\begin{aligned} \Delta f(x) &= f(x + 1) - f(x) \\ &= \sum_{i = 0}^n a_i(x + 1)^i - \sum_{i = 0}^n a_ix^i \\ &= \sum_{i = 0}^n a_i[(x + 1)^i - x^i] \end{aligned} \]我们只考虑 \(x_n\) 项得到可能得到它的只有这个式子：
\[a_n[(x + 1)^n - x^n] \]我们把 \((x + 1)^n\) 用二项式定理展开，因为只考虑 \(n\) 次项，所以我们只保留 \(x^n\) ，发现其系数为 \(1\) ，刚好和后面的项消掉。所以将数列差分一次后就会消掉最高次项。类似的， \(p\) 次差分后就会消掉 \(p\) 次项，所以这个数列的通项公式是一个关于 \(n\) 的 \(p\) 次多项式。
设数列 \(\{a_n\}\) 的通项公式为 \(a_n = \sum_{i = 1}^n i^k\) ，其差分数列的通项公式为 \(f(x) = x^k\) 是一个 \(k\) 次多项式，所以这个数列是一个关于 \(n\) 的 \(k + 1\) 次多项式。
那么我们为了确定这个 \(k + 1\) 次多项式，我们需要 \(k + 2\) 个点来确定。令这些点的坐标为 \(1 \sim k + 2\) ，即可 \(O(n)\) 求解。因为 \(i^k\) 是完全积性函数，可以线性筛。
给定一个不超过 \(n\) 次的多项式的 \(n+1\) 个点值 \(f(0),f(1) \dots f(n)\)，和一个正整数 \(m\)，求 \(f(m),f(m+1) \dots f(m+n)\) 。答案对 \(998244353\) 取模。
\(n \leq 1.6 \times 10^5\) ，\(n < m \leq 10^8\)
由插值公式可得：
\[\begin{aligned} f(m + x) &= \sum_{i = 0}^n f(i) \prod_{j \not = i} \dfrac{m + x - j}{i - j} \\ &= \sum_{i = 0}^n f(i) \dfrac{\dfrac{(m + x)!}{(m + x - n - 1)!}}{(m + x - i) (-1)^{n - i} i! (n - i)!} \end{aligned} \]令：
\[\begin{aligned} u_i &= \begin{cases} \dfrac{f(i)}{(-1)^{n - i} i! (n - i)!} & i \leq n \\ 0 & i > n \end{cases} \\ v_i &= \dfrac{1}{m - n + i} \end{aligned} \]可得：
\[f(m + x) = (u \times v)[n + x] \prod_{i = m + x - n}^{m + x} i \]NTT 即可。
inline void Lagrange(int *f, int n, int *res, int m) {
static int u[N], v[N];
for (int i = 0; i <= 2 * n; ++i) {
u[i] = i <= n ? 1ll * f[i] * sgn(n - i) % Mod * invfac[i] % Mod * invfac[n - i] % Mod : 0;
v[i] = mi(m - n + i, Mod - 2);
}
Poly::Mul(u, 2 * n + 1, v, 2 * n + 1, u);
int prod = 1;
for (int i = m - n; i <= m; ++i)
prod = 1ll * prod * i % Mod;
for (int i = 0; i <= n; ++i) {
res[i] = 1ll * u[n + i] * prod % Mod;
prod = 1ll * prod * mi(m + i - n, Mod - 2) % Mod * (m + i + 1) % Mod;
}
}