拉格朗日插值法

这个也没啥太特别，就是很快速的求出了一个多项式的某一项

直接上公式：

证明不想说，只是为了自己复习用

inline int lglr(int n,int *x,int *y,int xi){
    int ret=0;
    for(int i=0;i<=n;i++){
        int fz=1,fm=1;
        for(int j=0;j<=n;j++){
            if(i==j)continue;
            fz=fz*((xi-x[j])%mod+mod)%mod,fm=fm*((x[i]-x[j])%mod+mod)%mod;
        }
        ret=(ret+y[i]*fz%mod*ksm(fm,mod-2)%mod)%mod;
    }return (ret+mod)%mod;
}

拉格朗日插值法

原文：https://www.cnblogs.com/hzoi-fengwu/p/15313499.html