这个也没啥太特别,就是很快速的求出了一个多项式的某一项
直接上公式:
\[\huge f_i(x)=\frac{\prod\limits_{j\not = i}(x-x_j)}{\prod\limits_{j\not = i}(x_i-x_j)}*y_i \] \[\huge g(x)=\sum_{i=0}^nf_i(x) \]证明不想说,只是为了自己复习用
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;
}