拉格朗日插值

很久很久以前，有一个人叫拉格朗日，他发现了拉格朗日插值，可以求出给出函数 \(f(x)\) 的 \(n+1\) 个点，求出这个函数 \(f(x)\) 的值。

推论：

根据某些定理可知：
\(f(x)\equiv f(a)\bmod(x-a)\)

那么我们就可以把这个 \(n+1\) 个点的式子全部列出来。最终为

\(f(x)\equiv f(x_1)\bmod(x-x_1)\)

计算：

我们可以发现，这个式子特别类似于中国剩余定理的式子，那么根据中国剩余定理，我们可以设：

\(M=\prod_{i=1}^n{(x-x_i)},m[i]=\frac{M}{x-x_i}\)

继续，得到 \(m[i]\) 的逆元是 \(m[i]^{-1}=\prod_{j!=i} \frac{1}{x_i-x_j}\)

所以，最后中国剩余定理的值是：

\(f(x)=\sum_{i=1}^n y_im_im_i^{-1}\equiv \sum_{i=1}^n y_i \prod_{i!=j} \frac{x-x_j}{x_i-x_j}\)

因此，只要直接套到这个公式里就行了。

例题：

洛谷P4781

模板，直接上代码：(不会真有人不会算逆元吧(是我啊(那没事了)))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n,k,x[2005],y[2005],ans,s1,s2;
ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    } 
    return res%mod;
}
ll inv(ll x){return qmi(x,mod-2);}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&x[i],&y[i]);
    for(int i=1;i<=n;i++){
        s1=y[i]%mod;
        s2=1ll;
        for(int j=1;j<=n;j++)
            if(i!=j){
                s1=s1*(k-x[j])%mod;
                s2=s2*(x[i]-x[j])%mod;
            }
                
        ans+=s1*inv(s2)%mod;
    }
    cout<<(ans%mod+mod)%mod<<endl;
    system("pause");
    return 0;
}