拉格朗日插值法

过 $n+1$ 个横坐标互异的点 $(x_1,y_1),(x_2,y_2),\cdots,(x_{n+1},y_{n+1})$ 的 $n$ 次多项式恰为

$f(x) = \sum_{i=1}^{n+1} y_i \prod_{j\neq i} \dfrac{x-x_i}{x_j-x_i}$

证明

将 $n+1$ 个点代入显然得到结论。

模板

[洛谷P4781] 【模板】拉格朗日插值

给出 $n$ 个点，插值出多项式，并求出一个点值，朴素实现是 $O(n^2)$ 的。

如果要在取模下实现，记得先把分母都乘起来，然后统一求逆元，这样复杂度依然是 $O(n^2)$ 的。

参考代码：

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int MOD = 998244353;

int ksm(int a,int b){
    int r=1;
    while(b){
        if(b&1)r=(ll)r*a%MOD;
        a=(ll)a*a%MOD;
        b>>=1;
    }
    return r;
}
int inv(int x){return ksm(x,MOD-2);}

const int N = 2e3+5;
int px[N],py[N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n,k; cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>px[i]>>py[i];
    
    int ans = 0;
    for(int i=1;i<=n;i++){
        int num=1,deno=1; // 分子,分母
        for(int j=1;j<=n;j++){
            if(j==i)continue;
            num = (ll)num*(k-px[j]+MOD)%MOD;
            deno = (ll)deno*(px[i]-px[j]+MOD)%MOD;
        } 
        ans = (ans + (ll)num*inv(deno)%MOD*py[i]%MOD)%MOD;
    }

    cout << ans << '\n';
    return 0;
}

例题

[CF622F] The Sum of the k-th Powers

题意

求 $\sum_{i=1}^n i^k$ 对 $10^9+7$ 取模的值。

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

解法

通过魔法我们可以得出答案是关于 $n$ 的 $k+1$ 次多项式。

这时候 $O(k^2)$ 的朴素处理就不够了。但是，因为这里用来插值的点是任意的，我们不妨取 $1 \sim k+2$ 用来插值。

即

$f(x) = \sum_{i=1}^{k+2} y_i \prod_{j\neq i} \dfrac{x-j}{i-j}$

此时可以发现，上式中的分母就变成了两段阶乘！

化简可得

$f(x) = \sum_{i=1}^{k+2} (-1)^{k+2-i}y_i \cdot \dfrac{\left[\displaystyle\prod_{j < i}{(x-i)} \right]\left[\displaystyle\prod_{j > i}{(x-i)}\right]}{(i-1)!(k+2-i)!}$