拉格朗日插值学习笔记

· · 个人记录

拉格朗日插值学习笔记

概念

拉格朗日插值用于拟合一个函数。可以通过已知函数中的点拟合出函数。若为 n 次函数，则需要多于 n+1 个点。

做法

考虑构造 n+1 个函数，第 i 个函数 f_i 对应点 i 满足 f_i(X_i)=Y_i 且对于其他的点 j(i\neq j) 满足 f_i(X_j)=0。显然最后结果就为 \sum\limits_{i=1}^{n+1} f_i。

满足后者，我们只需要让函数 f_i 形如 \prod\limits_{j=1}^{n+1}(x-X_j)(i\neq j) 即可。考虑满足后者。

因为 0 的倍数为 0，所以给函数加系数不影响。当前函数 f_i 取 X_i 时为 \prod\limits_{j=1}^{n+1}(X_i-X_j)(i\neq j) 则让当前值变为 Y_i 可以乘 \frac{Y_i}{\prod\limits_{j=1}^{n+1}(X_i-X_j)(i\neq j)}。带入原函数则为

f_i(x)=\prod\limits_{j=1,i\neq j}^{n+1}(x-X_j)*\frac{Y_i}{\prod\limits_{j=1,i\neq j}^{n+1}(X_i-X_j)}

一般写成

f_i(x)=Y_i*\prod\limits_{j=1,i\neq j}^{n+1}\frac{(x-X_j)}{(X_i-X_j)}

则最终函数为

F(x)=\sum\limits_{i=1}^{n} f_i(x) F(x)=\sum\limits_{i=1}^{n} Y_i*\prod\limits_{j=1,i\neq j}^{n+1}\frac{(x-X_j)}{(X_i-X_j)}

代码（模板拉格朗日插值）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#define mod 998244353
#define int long long
using namespace std;
int n,k;
int x[100001],y[100001],ans;
int pow(int a,int b)
{
    int re=1;
    while(b)
    {
        if(b&1)
        {
            re*=a;
            re%=mod;
        }
        a*=a;
        a%=mod;
        b>>=1;
    }
    return re;
}
signed main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&x[i],&y[i]);
        x[i]%=mod;
        y[i]%=mod;
    }
    for(int i=1;i<=n;i++)
    {
        int mul=1,mul2=1;
        for(int z=1;z<=n;z++)
        {
            if(i==z) continue;
            mul*=(k-x[z])%mod;
            mul2*=(x[i]-x[z])%mod;
            mul%=mod;
            mul2%=mod;
        }
        ans+=mul*pow(mul2,mod-2)%mod*y[i]%mod;
        ans%=mod;
    }
    printf("%lld",(ans%mod+mod)%mod);
}