[学习笔记] 拉格朗日插值
0. 我们要干什么?
我们都知道,给定 \(n\) 个 \(x\) 坐标互异的点 \((x_i,y_i)\),可以唯一确定一个 \(n-1\) 次的多项式 \(f(x)\)。现在已知 \(n\) 个 \(x\) 坐标互异的点 \((x_i,y_i)\),计算出 \(f(k)\).
1. 拉格朗日插值
1.1. 公式
\[f(k)=\sum_{i=1}^n y_i\cdot \prod_{j\ne i}\frac{k-x_j}{x_i-x_j} \]可以发现,朴素求解一次是 \(\mathcal O(n^2)\) 的。
1.2. 推导
构造 \(n\) 个函数 \(f_i(x)\),使得 \(f_i(x)\) 过 \((x_i,y_i),(x_j,0)(j\ne i)\),则有 \(f(x)=\sum_{i=1}^n f_i(x)\).
设 \(f_i(x)=a\cdot \prod_{j\ne i}(x-x_j)\),显然这个函数必经 \((x_j,0)(j\ne i)\)。将 \((x_i,y_i)\) 代入函数得 \(a=\frac{y_i}{\prod_{j\ne i}(x_i-x_j)}\)。所以有
\[f_i(x)=y_i\cdot \frac{\prod_{j\ne i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)} \]得证。
1.3. 当 \(x\) 取值连续
不妨设 \(n\) 个点变成了 \((i,y_i)\)(事实上这种方法只要求 \(x\) 取值连续)。那么有
\[f(k)=\sum_{i=1}^ny_i\cdot \prod_{j\ne i}\frac{k-j}{i-j} \]维护 \(k-i\) 的前缀积与后缀积,再维护阶乘 \(\rm fac\),上式可以被表示为
\[f(k)=\sum_{i=1}^ny_i\cdot \frac{\text{pre}_{i-1}\cdot \text{suf}_{i+1}}{\text{fac}_{i-1}\cdot \text{fac}_{n-i}} \]需要注意一下符号。
1.4. 重心拉格朗日插值法
设 \(t_i=\frac{y_i}{\prod_{j\ne i}(x_i-x_j)}\),就有
\[f(k)=\left(\prod_{i=1}^n (k-x_i) \right)\cdot \sum_{i=1}^n \frac{t_i}{k-x_i} \]2. 例题
例 1.
\(\text{[TJOI 2018] }\)教科书般的亵渎
将题意转化为一次使用在空怪的 "亵渎" 可以消掉包含此空怪与之后的一段出现怪物,不妨在 \(0\) 号位放置一个空怪。那么得到 \(k=m+1\)。需要注意的是,如果从 \(n\) 开始有一段空怪,这些空怪并不用计入 \(k\) 的贡献。
现在计算每一次 "亵渎" 的贡献,假设这次 "亵渎" 在位置 \(p\),那么它的贡献就是 \(\big(\sum_{i=1}^{n-p}i^k-\) 空怪的贡献 \(\big)\)。事实上由于空怪数量很少,空怪的贡献可以硬算,所以问题实际上转化成了快速求解 \(\sum_{i=1}^n i^k\),其中 \(n\le 10^{13},m\le 50\).
由于 \(S_k(n)=\sum_{i=1}^n i^k\) 实际上是关于 \(n\) 的 \(k+1\) 次多项式,所以考虑拉格朗日插值,将 \(1\) 到 \(k+2\) 代进去算即可,由于 \(x\) 取值连续,所以可以做到 \(\mathcal O(k)\).