文章

4

粉丝

139

获赞

1

访问

4.1k

头像
拉格朗日插值法详解
P1597
发布于2023年4月19日 19:28
阅读数 923

拉格朗日插值法就是构造一个多项式,使得恰好在每一个x处取到对应的y
首先,n+1个点(xi,yi)若xi不同,则可以确定唯一的最高幂次不超过n的多项式。而如果题目直接或是间接给出了n+1个点,让我们求由这些点构成的多项式在某一个位置的取值,那么应用拉格朗日插值可以在O(n2 )的时间内解决这一问题

基本内容:

在这里插入图片描述

思路如下:
对于这个函数,要想在k=x[i]的时候取到y[i],并且y[i]仅在这一情况对答案有影响,就要构造出一项K[i]y[i],使得x仅在取到x[i]时K为1,其他情况K[i]为0。
于是,仿照中国剩余定理的思路,有了如下构造方式:
(1)首先,x≠x[i]时K[i]为0,就要让x取到除去x[i]外的任何值都为0,于是有了“累乘‘k-x[j]’”的思路;
(2)其次,如果简单地将y[i]与 累乘‘k-x[j]’ 结合,则x=x[i]时
该项为“累乘x[i]-x[j]",所以需要在每一项下面加上"除以x[i]-x[j]”
(3)最后将每一项加和,得到上式

拓展:x取值连续时的做法

有时候,问题仅要求求解x连续的情况。那么如果仅有一个k值需要代入f(k),就可以用下面的方法将复杂度变为O(n)

在这里插入图片描述

对于分子,维护出k的前缀积和后缀积,即:

在这里插入图片描述

在这里插入图片描述

由于最终求得的值一定为正数,故需判断一下正负号。
如果N-i为奇数,则分母要取负数(因为fac(N-i)表示的是绝对值,N-i为偶数的时候恰好所有负号消掉了)

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define il inline
#define re register
il int read()
{
	int s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){ if(c=='-') w=-1;c=getchar(); }
	while(c>='0'&&c<='9'){ s=(s<<...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发