题目背景
这是一道模板题
题目描述
由小学知识可知，nn个点(x_i,y_i)(xi,yi)可以唯一地确定一个多项式
现在，给定nn个点，请你确定这个多项式，并将kk代入求值
求出的值对998244353998244353取模
输入格式
第一行两个正整数n,kn,k，含义如题
接下来nn行，每行两个正整数x_i,y_ixi,yi，含义如题
输出格式
一个整数表示答案
输入阳历：
3 100
1 4
2 9
3 16
输出样例：
10201
所周知，n + 1n+1个xx坐标不同的点可以确定唯一的最高为nn次的多项式。在算法竞赛中，我们常常会碰到一类题目，题目中直接或间接的给出了n+1n+1个点，让我们求由这些点构成的多项式在某一位置的取值
一个最显然的思路就是直接高斯消元求出多项式的系数，但是这样做复杂度巨大(n^3)(n3)且根据算法实现不同往往会存在精度问题
而拉格朗日插值法可以在n^2n2的复杂度内完美解决上述问题
假设该多项式为f(x)f(x), 第ii个点的坐标为(x_i, y_i)(xi,yi)，我们需要找到该多项式在kk点的取值
根据拉格朗日插值法
f(k) = \sum_{i = 0}^{n} y_i \prod_{i \not = j} \frac{k - x[j]}{x[i] - x[j]}f(k)=i=0∑nyii̸=j∏x[i]−x[j]k−x[j]
乍一看可能不是很好理解，我们来举个例子理解一下
假设给出的三个点为(1, 3)(2, 7)(3, 13)(1,3)(2,7)(3,13)
直接把$f(k)展开$
f(k) = 3 \frac{(k - 2)(k - 3)}{(1 - 2)(1 - 3)} + 7\frac{(k-1)(k-2)}{(2 - 1)(2-3)} + 13\frac{(k-1)(k-2)}{(3 -1)(3-2)}f(k)=3(1−2)(1−3)(k−2)(k−3)+7(2−1)(2−3)(k−1)(k−2)+13(3−1)(3−2)(k−1)(k−2)
观察不难得到，如果我们把x_ixi带入的话，除第ii项外的每一项的分子中都会有x_i - x_ixi−xi，这样其他的所有项就都被消去了
因此拉格朗日插值法的正确性是可以保证的
代码：
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#define int long long
#define mod 998244353
const int N = 2050;
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int power(int a,int b)
{
int res=1;
for(;b;b>>=1)
{
if(b&1)res=(res%mod*a%mod)%mod;
a=(a%mod*a%mod)%mod;
}
return res%mod;
}
int x[N],y[N],n,ans,v;
signed main()
{
n=read();
v=read();
for(int i=1;i<=n;i++)
{
x[i]=read();y[i]=read();
}
for(int i=1;i<=n;i++)
{
int k=1;
for(int j=1;j<=n;j++)if(i!=j)k=k*(x[i]+mod-x[j])%mod;
k=power(k,mod-2);
for(int j=1;j<=n;j++)
{
if(i!=j)k=k*(v+mod-x[j])%mod;
}
k=k*y[i]%mod;
ans=(ans+k)%mod;
}
printf("%d\n",ans);
return 0;
}