前言

学FFT的时候碰到了这个神奇的东西，于是记录一下。

拉格朗日插值法

可知由$n+1$个不同$x$坐标的点可以为以确定一个最高次数为$n$的多项式。

那么给定这$f(x)$对应的$n+1$个点，并求$f(a)$

拉格朗日插值法可以在$O(n^2)$复杂度内解决问题（当然也可以用高斯消元$O(n^3)$解决）

模板题 洛谷 P4781

给定$(x_0,y_0),...,(x_k,y_k)$，求$f(x)$，结果对$998244353$取余

假设任意两个$x_i,x_j(i\ne j)$都不相同，那么应用拉格朗日插值公式得到的插值多项式为：

$L(x)=\sum_{j=0}^k y_jl_j(x)$

其中$l_j(x)$为拉格朗日基本多项式，表达式为

$l_j(x)=\prod_{i=0,i\ne j}^k \frac{x-x_i}{x_j-x_i}$

其特点是在$x_j$上取值为1，其他点$x_i$上取值为0

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int maxn = 2e3 + 1000;
const ll mod = 998244353;

ll n, k;
ll x[maxn], y[maxn]; 

ll inv(ll val){
    ll ret = 1, t = mod-2;
    while(t){
        if(t & 1) ret = ret * val % mod;
        t >>= 1;
        val = val * val % mod;
    }
    return ret;
}

signed main(){
    cin >> n >> k;
    for(int i=0; i<n; i++) cin >> x[i] >> y[i];
    ll ans = 0, t1, t2;
    for(int i=0; i<n; i++){
        t1 = t2 = 1;
        for(int j=0; j<n; j++){
            if(j == i) continue;
            t1 = t1 * ((x[i] - x[j] + mod) % mod) % mod;
            t2 = t2 * ((k - x[j] + mod) % mod) % mod;
        }
        ans += y[i] * t2 % mod * inv(t1) % mod;
        ans %= mod;
    }
    cout << ans << '\n';
}

重心拉格朗日插值法

可以发现，每当我们添加一个新点，在上述方法中就得完全重新计算。

下面是拉格朗日插值法的一种改进。

令$l(x)=(x-x_0)(x-x_1)...(x-x_k)$

则$l_j(x)=\frac{l(x)}{x-x_j}\frac{1}{\prod_{i=0,i\ne j}^k(x_j-x_i)}$

定义重心权

$w_j=\frac{1}{\prod_{i=0,i\ne j}^k(x_j-x_i)}$

则$l_j(x)=l(x)\frac{w_j}{x-x_j}$

拉格朗日插值多项式变为$L(x)=l(x)\sum_{j=0}^k y_j\frac{w_j}{x-x_j}$

每当插入一个点$(x_{k+1},y_{k+1})$，则只需对每个$w_i$除以$x_i-x_{k+1}$即可得到新的重心权

重新计算的复杂度为$O(n)$

参考资料

维基百科-拉格朗日插值法 (opens new window)