n + 1个x坐标不同的点可以确定唯一的最高为n次的多项式
知道n+1个点,求第k项。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
#define pb push_back
#define pr make_pair
using namespace std;
const int mod=998244353;
const int maxn=2100;
ll x[maxn],y[maxn],n,k;
ll mypow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main(void)
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&x[i],&y[i]);
ll ans=0;
for(int i=1;i<=n;i++)
{
ll res=y[i],sum=1;
for(int j=1;j<=n;j++)
{
if(j!=i)
{
res=res*(k-x[j])%mod;
sum=sum*(x[i]-x[j])%mod;
}
}
sum=mypow((sum+mod)%mod,mod-2);
ans=(ans+sum*(res+mod))%mod;
}
printf("%lld\n",ans);
return 0;
}