题意
给定(n)个点((x_i,y_i))，请你确定这个多项式，并将(k)代入求值
求出的值对(998244353)取模
思路
学习了一下拉格朗日插值法(最菜的那种),其实还是挺好懂的
按照朴素思路，我们是构造一个矩阵，然后高斯消元法(O(n^3)),妥妥的(TLE)
那么
拉格朗日插值法的思路很简单，按照题目样例一给的三个点：
- 1 4
- 2 9
- 3 16
我们假设有以下(3) 个函数：
- (G_1(x)=(x-2)(x-3))
- (G_2(x)=(x-1)(x-3))
- (G_3(x)=(x-1)(x-2))
因此，显然有
(G_1(2)=G_1(3)=0 , G_2(1)=G_2(3)=0 , G_3(1)=G_3(2)=0)
所以我们需要的原函数可以写为：
$f(x)=A_1G_1(x)+A_2G_2(x)+A_3G_3(x) $
那就很显然有
[ left{egin{aligned}
\f(1)=A_1G_1(1)+A_2 imes0+A_3 imes 0=A_1G_1(1)
\f(2)=A_1 imes 0+A_2G_2(2)+A_3 imes 0=A_2G_2(2)
\f(3)=A_1 imes 0+A_2 imes 0+A_3G_3(3)=A_3G_3(3)
end{aligned}
ight.
]
所以把点值回带就能算(A)的值
总结一下并推广到其他情况,我们先构造了
(G_i(x)=prod_{j=1&j
eq i}^n(x-x_j))
因为 $$A_i=frac{y_i}{G_i(x_i)}$$
倒代入点的坐标得：
[f(k)=sum_{i=1}^n A_i G_i(k)
]
[=sumfrac{y_i}{G_i(x_i)}*G_i(k)
]
公式整理得：
[f(x)=sum_{i=1}^{n} y_i imes(prod_{j
eq i }frac{x-x_j}{x_i-x_j})
]
然后代码实现(O(n^2))就非常简单了,注意逆元可以乘起来求一次,不需要每次求
#include <bits/stdc++.h>
const int N=2005;
int n,k,x[N],y[N],ans;
const int mu=998244353;
int ksm(int x,int y){
int ans=1;
for (;y;y>>=1,x=1ll*x*x%mu)
if (y&1) ans=1ll*ans*x%mu;
return ans;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for (int i=1;i<=n;i++){
int t=1,t2=1;
for (int j=1;j<=n;j++){
if (j==i) continue;
t=1ll*t*(k-x[j])%mu;
t2=1ll*t2*(x[i]-x[j])%mu;
}
ans=(ans+t*1ll*y[i]%mu*ksm(t2,mu-2))%mu;
}
printf("%d
",(ans+mu)%mu);
}
如果要求多项式的话，那可以直接暴力算出 (A_i=frac{y_i}{G_i(x_i)})，然后乘上相应的 (G_i)，(G_i) 可以先算出 (prod (x-x_i))，然后每次除掉相应项即可
void mul(int c){
for (int i=W;i>=0;i--){
reduce(f[i+1]+=f[i]-mu);
f[i]=(ll)f[i]*c%mu;
}
}
void div(int c){
int inv=ksm(c,mu-2);
memcpy(g,f,sizeof(g));
for (int i=0;i<=W;i++){
g[i]=(ll)g[i]*inv%mu;
reduce(g[i+1]-=g[i]);
}
}
void lglr(){
f[0]=1,W=0;
for (int i=0;i<=n;i++)
mul(mu-x[i]),W++;
for (int i=0;i<=n;i++){
div(mu-x[i]);
int s=1;
for (int j=0;j<=n;j++)
if (i!=j) s=(ll)s*(x[i]-x[j])%mu;
s=(s+mu)%mu;
int A=(ll)fy[i]*ksm(s,mu-2)%mu;
for (int j=0;j<=n;j++)
reduce(ans[j]+=(ll)g[j]*A%mu-mu);
}
}
后记
多项式一窍不通,以后要努力啊