拉格朗日插值法学习-白红宇

拉格朗日插值法学习

阅读量：6305 次

发布时间：2019-06-22

本文共 1040 字，大约阅读时间需要 3 分钟。

有几个很好的博客：

https://www.cnblogs.com/ECJTUACM-873284962/p/6833391.html

洛谷模板：

// luogu-judger-enable-o2#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define dul(p) (((p)%MOD+MOD)%MOD)using namespace std;const int maxn=1000000+10101;const int MOD=998244353;inline ll read(){ ll x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0'; return x*f;}ll ans,n,k,x[maxn],y[maxn];ll power(ll x,ll y){ ll ans=1; while(y){ if(y&1)ans=(ans*x)%MOD; x=(x*x)%MOD; y>>=1; } return dul(ans);}int main(){ n=read();k=read(); for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(); for(int i=1;i<=n;i++){ ll a1=1,b1=1; for(int j=1;j<=n;j++){ if(i==j)continue; a1=a1*(k-x[j])%MOD; b1=b1*(x[i]-x[j])%MOD; } ans=dul(ans+dul(y[i]*a1%MOD*power(b1,MOD-2))); } printf("%lld",dul(ans)); return 0;}