拉格朗日插值公式
任给定\(F\)中\(2n+2\)个数\(x_1，x_2，…，x_{n+1}，y_1，y_2，…，y_{n+1}，\)其中\(x_1，x_2，…x_{n+1}\)互不相同，则存在唯一的次数不超过n的多项式\(f(x)\)，满足\(f(x_i)=y_i{\color{white}..}(i=1，2，…，n+1)\)，这里
\[f(x)=\sum_{i=1}^{n}{y_i\cdot(\prod_{j\ne i}^{1\le j\le n}\frac{(x-x_j)}{(x_i-x_j)})} \]叫做拉格朗日插值公式。
公式的几何解释是：存在唯一的次数不超过\(n\)的抛物线
\[{\color{white}..} y=a_0+a_1 \cdot x+a_2 \cdot x^2+…+a_n \cdot a^n {\color{white}..} \]通过平面上的给出的\(n+1\)个点\(M_1(x_1，y_1)，M_2(x_2，y_2)，…，M_{n+1}(x_{n+1}，y_{n+1})\)。
特别地，如对于自变数的两个值，给出了线性函数的\((n=1)\)对应值，这线性函数就被确定。从几何方面说，直线由其两点确定，即：
\[y=y_1 \cdot \frac{x-x_2}{x_1-x_2}+y_2\cdot\frac{x-x_1}{x_2-x_1} \]code
给定这 \(n\) 个点，确定这个 \(n-1\) 次多项式，并求出 \(f(k) \mod 998244353\) 的值。
题目链接
题解
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long
using namespace std;
namespace Q{
il int rd(){
ri int x=0,f=1;ri char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
return x*f;
}
il void wt(int x){
if(x<0) x=-x,putchar('-');
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
}
cs int mod=998244353,N=2e3+5;
int n,k,x[N],y[N];
il int qpow(int a,int b){
int as=1;
while(b){
if(b&1) as=as*a%mod;
a=a*a%mod,b>>=1;
}
return as;
}
signed main(){
n=Q::rd(),k=Q::rd();
for(ri int i=1;i<=n;++i){
x[i]=Q::rd(),y[i]=Q::rd();
}
int as=0;
for(ri int i=1;i<=n;++i){
int s=1;
for(ri int j=1;j<=n;++j){
if(i==j) continue;
s=s*(k-x[j])%mod*qpow(x[i]-x[j],mod-2)%mod;
}
as=(as+s*y[i]%mod)%mod;
}
Q::wt((as%mod+mod)%mod);//!!!!!!!
return 0;
}