瞎JB说几句拉格朗日插值

众所周知由$m$个点（第$i$个点为$x_i,y_i$）可以确定一个$n(m>n)$次多项式在$k$时的值，对$p$取模。

那么这个式子是啥呢？

答案就是拉格朗日插值，具体公式如下：

$f(k)=\sum_{i=1}^m y_i (\prod_{j=1,i\ne j}^n \frac{k-x_j}{x_i-x_j})\bmod p$

那么怎么求这个式子呢？

观察主体是暴力，$O(n^2)$。

接下来注意到$\prod_{j=1,i\ne j}^n$里有一个$i\ne j$，原因是如果$i=j$，那么$x_i-x_j=0$，分母就变成了$0$。

$\frac{k-x_j}{x_i-x_j}$的话，显然下面的式子要求$x_i-x_j$模$p$的逆元，再乘上$k-x_j$，该部分时间复杂度$O(\log p)$，总时间复杂度$O(n^2\log p)$。

代码：

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
//#define moda 998244353
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const ll N=100001,inf=0x3f3f3f3f,moda=998244353;
inline ll read(){
	ll date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
ll ksm(ll a,ll b){
    ll ans=1ll,base=a;
    while(b){
        if(b&1){
            ans*=base;ans%=moda;
	    }
	    base*=base;base%=moda;
	    b>>=1;
	}
    return ans;
}
ll n,m,a[N],b[N],k,ans;
int main(){
	m=read(),n=m-1;k=read();
	fs(i,1,m,1){
		a[i]=read(),b[i]=read();
	}
	fs(i,1,m,1){
		ll joga=b[i]%moda,kaya=1ll;
		fs(j,1,m,1){	
			if(j!=i){
				joga=joga*(k-a[j])%moda;
				kaya=kaya*((a[i]-a[j]%moda)%moda)%moda;
				//joga%=moda;
			}
		}
		ans+=joga*ksm(kaya,moda-2)%moda;ans=(ans+moda)%moda;
	}
	printf("%lld",ans);
	return 0;
}