【洛谷4781】 【模板】拉格朗日插值

这个东西太 nb 了 ~ 

code: 

#include <bits/stdc++.h>   
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;          
const int mod=998244353,N=2004;   
int x[N],y[N];     
inline int qpow(int x,int y) 
{
    int tmp=1;  
    for(;y;y>>=1,x=1ll*x*x%mod)    if(y&1)    tmp=1ll*tmp*x%mod;   
    return tmp;   
}
int INV(int x) { return qpow(x,mod-2);  }
int main() 
{ 
    // setIO("input");   
    int n,k,i,j,ans=0;        
    scanf("%d%d",&n,&k);   
    for(i=1;i<=n;++i)    scanf("%d%d",&x[i],&y[i]);      
    for(i=1;i<=n;++i) 
    {
        int tmp1=1,tmp2=1;  
        for(j=1;j<=n;++j)   if(i!=j)   tmp1=1ll*tmp1*(x[i]-x[j]+mod)%mod,tmp2=1ll*tmp2*(k-x[j]+mod)%mod;   
        ans=1ll*(ans+1ll*INV(tmp1)*tmp2%mod*y[i]%mod)%mod;     
    }
    printf("%d
",ans);   
    return 0;  
}