存在性和唯一性的证明以后再补。。。。
拉格朗日插值,emmmm,名字挺高端的:joy:
它有什么应用呢?
我们在FFT中讲到过
设n-1次多项式为
y=\sum_{i=0}^{n-1}a_i x^i
有一个显然的结论:如果给定n个互不相同的点(x,y),则该n-1次多项式被唯一确定
那么如果给定了这互不相同的n个点,
利用拉格朗日插值,可以在O(n)的时间内计算出某项的值,还可以在O(n^2)的时间复杂度内计算出给定的x所对应的y
那么如何计算呢?
不啰嗦了,直接给公式吧,至于这个公式怎么来的以后再补充
若对于n-1次多项式,给定了n个互不相同的(x,y)
那么对于给定的x,第i项的值为
l(i)=y_i\prod_{j=1,j\neq i}^{n} \dfrac{x-x_j}{x_i-x_j}
所对应的y为
y=\sum_{i=1}^{n} l(i)
=\sum_{i=1}^{n}y_i\prod_{j=1,j\neq i}^{n}\dfrac{x-x_j}{x_i-x_j}
利用这个公式,就可以进行计算啦
#include<cstdio>
int x[1001],y[1001];
int N,ans=0;
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d%d",&x[i],&y[i]);
int X;//待求的x
scanf("%d",&X);
for(int i=1;i<=N;i++)
{
int tmp=y[i];
for(int j=1;j<=N;j++)
{
if(i==j) continue;
tmp=tmp*(X-x[j])/(x[i]-x[j]);
}
ans+=tmp;
}
printf("%d",ans);
return 0;
}