首页 > 其他分享 >【小记】拉格朗日插值

【小记】拉格朗日插值

时间:2023-08-22 22:13:13浏览次数:40  
标签:拉格朗 插值 LL ne ret int 小记

拉格朗日插值是知道\(n\)次多项式在\(n+1\)个点的点值,快速求出\(f(x')\)的算法

结论

拉格朗日插值本质上就是该式子,首先我们知道的点值为当\(x=x_i\)时\(f(x)=y_i\)

\[f(x)=\sum_{i=0}^{n}y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j} \]

推导

首先假设我们考虑第\(i\)个点值。

那么我们先将另外\(n\)个点值,映射到\(x\)轴上。

即我们考虑构造函数\(g_i(x)\)当\(\forall j\ne i\)时\(g_i(x_j)=0\),且\(g_i(x_i)=y_i\)

那么显然的\(f(x)=\sum_{i=0}^{n}g_i(x)\)

并且可以发现

\[g_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j} \]

是满足条件的构造

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=998244353;
LL fpow(LL a,LL b){LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
	if(b&1)ret=ret*a%mod;
	return ret;
}
const int N=2e3+5;
LL X[N],Y[N];
int main(){
	LL n,k,ans=0,now;
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	scanf("%d%d",&X[i],&Y[i]);
	for(int i=1;i<=n;i++){
		now=Y[i];
		for(int j=1;j<=n;j++)if(i^j)
		now=now*(k-X[j]+mod)%mod*fpow(X[i]-X[j]+mod,mod-2)%mod;
		ans=(ans+now)%mod;
	}
	printf("%lld",ans);
	return 0;
}

标签:拉格朗,插值,LL,ne,ret,int,小记
From: https://www.cnblogs.com/dzrblog/p/17649822.html

相关文章

  • ArcMap栅格重采样:最邻近分配、众数算法、双线性插值、三次卷积插值
      本文介绍在ArcMap软件中,实现栅格图像重采样的具体操作,以及不同重采样方法的选择依据。  在文章ArcPy批量掩膜、重采样大量遥感影像中,我们介绍了基于Python中Arcpy模块对栅格图像加以批量重采样的方法;而在ArcMap软件中,我们可以实现不需要代码的栅格重采样操作;本文就对这一操......
  • 日常工具使用小记录 (daily tool usage snippet)
     1.如何上传本地文件至服务器(howtouploadlocalfilestoserver)1.1启动本地server假设本地目录C:/your_home/tmp,该目录下有文件test.txt cdc:/your_home/tmppython-mSimpleHTTPServer8081//新开另一个命令窗口openanothercmdtabifconfig//......
  • 「Log」2023.8.21 小记
    序幕七点到校,管理整理博客。然后开始写博客,SAM的。学长开始讲题,2-SAT,还算好理解,写完博客过了下板子题。\(\color{royalblue}{P4782【模板】2-SAT问题}\)板子。\(\text{Link}\)间幕\(1\)吃饭,学长开始讲LCT。和SAM同样抽象的东西。好消息是代码跟SAM一样较为好写......
  • 8.21 模拟赛小记
    A.吃饭路上也要锻炼,原P3505[POI2010]TEL-Teleportation咱现在思路通了,代码实现可能得鸽一鸽。两个强强的博客:https://www.cnblogs.com/stoorz/p/12182770.html,https://www.cnblogs.com/reywmp/p/14014611.html。是很难的思维题,涉及乘法原理和图论,用到了分层思想。统计答案时......
  • FFT 小记
    目录复数单位复数根PolyFFTEnd参考资料由于懒,所以没图。写得时候有点抽风,可能有typo,望指出。复数复数表述为\(a+b\timesi\),其中\(i\)是复数单位\(\sqrt{-1}\),同时由此可得\(i^2=-1\)。称\(a\)是实部(下文简称real),\(b\)是虚部(简称imag)。对于一个实数,其real等于其......
  • 小记
    1.路由跳转及传参import{withRouter,RouteComponentProps}from'react-router';classReplenishmentOrderextendsComponent<TProps&RouteComponentProps,TState>{constructor(props:RouteComponentProps){super(props);......
  • 8.18 模拟赛小记 & 学习
    谔谔谔谔。菜翻天。今天模拟赛题目传送门。A.跳蚤市场(mid)话说我才看到这个英文名字叫mid。然后就是手写lower_bound和upper_bound优化前缀和。B.组合问题(anm)这个错排之前上课讲过于是一眼了。可惜没看longlong祖宗十八代都被炸死了。C.旅行(day)图论题。D.购物(t......
  • 「Log」2023.8.17 小记
    序幕早上到校先摆,然后开调代码。大分块对拍调调调。学长开始讲平衡树。平衡树平衡树平衡树!学完了,点午饭吃午饭。学主席树。主席树主席树主席树!学完了点晚饭吃完饭。用chatGPT写了点文章,乐坏了。继续卡常。\(\color{black}{P4119\[Ynoi2018]\未来日记}\)详见「「No......
  • 「Log」2023.8.16 小记
    序幕早上昏迷,九点才到校,少听了四道题,问题不大。点咖啡喝。SAM题也抽象。线段树合并,不会。写个AC自动机板子。\(\color{royalblue}{P3808\【模板】AC\自动机(简单版)}\)板子。\(\text{Link}\)\(\color{royalblue}{P3796\【模板】AC\自动机(加强版)}\)板子。\(\text{Li......
  • 恋爱小记
    也不知道为啥要写,就是当给自己看的,并作为纪念,以后纪念日能找素材?8.14rp极高划水8.15rp极低,遵循rp守恒上午她说自己静静,然后一个小时后心态崩溃说分手,我知道她肯定乱想了,然后我拼命拉,把我能想到的方法都试了,最后还是我说,你要分,将来等着吧(把她吓到了)。然后才慢慢跟我说了......