求dalao看一下这个蒟蒻的拉插qwq
查看原帖
求dalao看一下这个蒟蒻的拉插qwq
613082
qscisQJing楼主2022/5/6 13:36
#include<iostream>
using namespace std;
#define ll long long
const int MAXN=1e4+5,mod=998244353;
ll x[MAXN],y[MAXN];
ll pow(ll a,ll b)
{
	a%=mod;
	ll ans=1,sum=a;
	while(b>0)
	{
		if(b&1)ans=sum*ans%mod;
		sum=sum*sum%mod;
		b>>=1;
	}
	return ans;
}
ll inv(ll x)
{
	return pow(x,mod-2);
}
int main()
{
	int n,k;
	ll ans=0;
	cin>>n>>k;
	for(int i=1;i<=n;i++)scanf("%d%d",x+i,y+i);
	for(int i=1;i<=n;i++)
	{
		ll _sum1=1,_sum2=1;
		for(int j=1;j<=n;j++)
			if(i!=j)_sum1*=k-x[i],_sum1%=mod,_sum2*=inv(x[j]-x[i]),_sum2%=mod;
		ans+=y[i]*_sum1*inv(_sum2);
		ans%=mod;
	}
	cout<<ans;
	return 0;
}
2022/5/6 13:36
加载中...