问题

给定 $n$ 个点，可确定一个多项式 $y=f(x)$ ，要求确定这个多项式并求出 $f(k)$

拉格朗日（Lagrange）插值公式

搬运

令 $L_n(x)=f(x)$

---

n=1

有

由点斜式可以得到

其中

这里 $l_k(x)$ 和 $l_{k+1}$ 称作线性插值基函数。

---

n=2

有

构造

易得

---

一般情况

$L_n(x)=l_0(x)\ast y_0+l_1(x)\ast y_1+l_2(x)\ast y_2+...+l_n(x)\ast y_n$

其中

于是

---

因此，求 $f(k)$ 直接将 $k$ 带入即可

时间复杂度 $O(n^2)$

$O(n^2)$求系数 留坑

高斯消元 $O(n^3)$ 求系数

代码

模板求 $f(k)$

#include<bits/stdc++.h>
#define LL long long
#define mod 998244353
using namespace std;
const int N=2e3+9;
int n;
LL k,ans;
LL x[N],y[N];
LL Inv(LL a,LL b)
{LL tot=1LL;while(b){if(b&1) (tot*=a)%=mod;(a*=a)%=mod; b>>=1;}return tot;
}
LL Lagrange()
{for(int i=1;i<=n;i++){LL fz=1LL,fm=1LL;for(int j=1;j<=n;j++)if(i!=j){(fz*=(k-x[j]))%=mod;(fm*=(x[i]-x[j]))%=mod;}(ans+=y[i]*fz%mod*Inv(fm,mod-2)%mod+mod)%=mod;}return ans;
}
int main()
{scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);printf("%lld\n",Lagrange());return 0;
}