对于 \(n\) 个点 \((x_i,y_i)\)，\(x_i\) 互不相同，则我们可以 唯一 确定一个 \(n-1\) 次多项式经过这 \(n\) 点。
1. 算法介绍
1.1 拉格朗日插值
拉格朗日插值的核心思想是每次只考虑一个点值，将其他点值都视作 \(0\)，即对于每一个点 \((x_i,y_i)\)，我们构造一个函数 \(f_i(x)\)。
- 当且仅当 \(x = x_i\) 时 \(f_i(x) = y_i\)，当 \(x = x_j(j \not = i)\) 时，\(f_i(x) = 0\)。
这样我们可以构造出经过所有点的函数 \(f(x) = \sum f_i(x)\)。
则我们首先对于每个点 \((x_i,y_i)\)，设 \(f_i(x) = \prod\limits_{j \not = i}(x - x_j)\)，则显然可以满足上述条件，而我们又要满足 \(f(x_i) = y_i\)，则我们可以构造:
\[f(x) = \sum\limits_{i=1}^n y_i \prod\limits_{i \not = j} {\dfrac {x - x_j} {x_i - x_j}} \]这样我们可以轻松的用 \(\mathcal{O}(n^2)\) 的复杂度解决。
直接套式子即可，逆元可以乘完再逆，写的时候脑子宕机了。
int main(){
n = read(),k = read();
for(int i = 1;i <= n;i++)x[i] = read(),y[i] = read();
ll ans = 0;
for(int i = 1;i <= n;i++){
ll s = y[i] % mod;
for(int j = 1;j <= n;j++){
if(i == j)continue;
s = s * (k - x[j] + mod) % mod;
s = s * ksm((x[i] - x[j] + mod) % mod,mod - 2) % mod;
}
(ans += s) %= mod;
}
printf("%lld\n",ans);
return 0;
}
1.2 一些小优化
当这些点值是 \((i,y_i)\) 时，则我们可以分开处理 \(\prod\limits_{i \not = j}x - j\) 与 \(\prod\limits_{i \not = j}i - j\)。
前者我们可以首先算出 \(\prod \limits x - j\)，求的时候除个 \((x - i)\) 即可。
后者我们可以分成 \(j < i\) 与 \(j > i\) 两个部分，求出答案是 \((i-1)! \times (n-i)! (-1)^{n-i}\)。
预处理逆元，复杂度 \(\mathcal{O}(n\log{V})\)。
例题: CF622F The Sum of the k-th Powers
即求 \(\sum\limits_{i=1}^n i^k\)。
\(n\) 太大，我们考虑关于 \(k\) 的复杂度。
首先我们可以知道这是一个关于 \(n\) 的 \(k+1\) 次多项式，我们只需要暴力求出前 \(k+2\)，即可拉插，复杂度 \(\mathcal{O}(n\log{V})\)
-
如何证明是一个 \(k+1\) 次多项式呢？
我们可以归纳证明: 首先懒得奠基。
假设该结论对所有 \(k < m\) 都成立，则现在证明 \(k = m\) 时成立。
首先有 \((i+1)^{m + 1} - i^{m + 1} = \sum\limits_{j=0}^m\dbinom {m+1} j i^j\)。
我们对所有的 \(i\) 求和，左边是个裂项，答案为 \((n+1)^{m+1} - 1\)。
有 $$(n + 1)^{m+1} - 1 = \sum_{i=1}^{n} \sum_{j=0}^m \dbinom {m+1} j i^j = \sum_{j=0}^m\dbinom {m+1} j \sum_{i=1}^n i^j$$
把右边 \(j = m\) 移项得 $$\sum_{i=1}^{n} i^m = (n + 1)^{m+1} - 1 - \sum_{j=0}^{m-1}\dbinom {m+1} j \sum_{i=1}^n i^j$$
左半部分次数为 \(m + 1\)，右半部分最大次数为 \(m - 1 + 1 = m\)，证毕。
1.3 多项式快速插值
不会