首页 > 其他分享 >拉格朗日插

拉格朗日插

时间:2024-03-22 18:55:06浏览次数:23  
标签:pre 拉格朗 inv up mul prod

拉格朗日插

拉格朗日插值:给定 \(n+1\) 个点 \((x_i,y_i)\),确定一个 \(n\) 次多项式 \(f\) 对其求值。

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

正确性可以通过带入 \(x_i\) 验证,配合小学数学知识。

cin >> n >> k, --n;
up(i,0,n) cin >> x[i] >> y[i];
up(i,0,n) up(j,0,n) inv[i][j]=ksm(x[i]-x[j],P-2);
up(i,0,n) {
	int mul=y[i];
	up(j,0,n) if(i^j) mul=mul*(k-x[j])%P*inv[i][j]%P;
	f=(f+mul)%P;
}
cout << (f%P+P)%P;

连续取值的拉格朗日插

连续取值的拉格朗日插:

\[f(k)=\sum_{i=0}^{n}y_i\prod_{i\neq j}\frac{k-j}{i-j} \]

考虑处理 \(pre[i]=\prod_{j=0}^{i}k-j,suf[i]=\prod_{j=i}^n k-j,fac[i]=\prod_{j=0}^ii\),那么有如下柿子,注意 \(n-i\) 为奇数时应取负号 >w<

\[f(k)=\sum_{i=0}^n y_i\frac{pre[i-1]\times suf[i+1]}{fac[i-1]\times fac[n-i]} \]


k 次幂和

观察可得 \(\sum_{i=1}^n i^k\) 是一个 \(k+1\) 次多项式可以带入 \(k+2\) 个值拉插求求,复杂度 \(O(n)\)。证明本来想要因为我又菜又笨又懒就算了,啊啊啊看官见笑了呜呜呜诶诶诶诶诶诶(

inv[0]=inv[1]=mul[0]=1;
up(i,2,2e6) inv[i]=inv[P%i]*(P-P/i)%P;
up(i,1,2e6) mul[i]=mul[i-1]*inv[i]%P;
cin >> n >> k, pre[0]=n, suf[k+1]=n-k-1;
up(i,1,k+1) pre[i]=pre[i-1]*(n-i)%P;
dn(i,k,  0) suf[i]=suf[i+1]*(n-i)%P;
up(i,0,k+1) {
	y=(y+ksm(i,k))%P;
	int qwq=((k+i)&1)?y:-y;
	if(i>0) qwq=qwq*pre[i-1]%P*mul[i]%P;
	if(i<k+1) qwq=qwq*suf[i+1]%P*mul[k+1-i]%P;
	out=(out+qwq)%P;
}
cout << (out+P)%P;

重心拉格朗日插

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

其实就是这样子求值快一点点。

标签:pre,拉格朗,inv,up,mul,prod
From: https://www.cnblogs.com/chelsyqwq/p/18090261

相关文章

  • 【Python】拉格朗日Lagrange插值与牛顿Newton插值求解
    实验原理熟悉并掌握Lagrange插值的构造原理;会计算在给定点的函数值Lagrange插值是一种基于Lagrange基函数的插值方法。给定一组数据节点(x,y),其中x是自变量,y是因变量,其插值的目标是构造一个多项式函数,通过这个多项式函数来拟合已知的数据节点,并用于对其他未知点进行插值预......
  • 拉格朗日插值
    插值:已知平面直角坐标系上的\(n\)个点,找出一个函数\(f(x)\)过这\(n\)个点,这样的函数有无限多个。拉格朗日插值:首先他构造了\(n\)个函数,第\(i\)个是\(f_i(x)=\left\{\begin{matrix}y_i&x=x_i\\0&x=x_j(j\nei)\end{matrix}\right.\)。对于其余的\(x\),我们并不关心。这......
  • 均值不等式证明(拉格朗日乘数法)
    Part1求证:\(\frac{n}{\sum_{i=1}^{n}\frac{1}{y_i}}\leq({\prod_{i=1}^{n}y_i})^{\frac{1}{n}}\)\(y_i\)为正实数\(n\geq3\)证明:令\(x_i\)=\(y_i^{\frac{1}{n}}\)且\(x_i\)为正实数原命题等价于:\[{\prod_{i=1}^{n}x_i}-\frac{n}{\sum_{i=1}^{n}\......
  • P5667 拉格朗日插值2
    由拉格朗日插值公式得:\[f(x)=\sum_{i=0}^nf(i)\prod_{j\nei}\dfrac{x-j}{i-j}=\sum_{i=0}^n\dfrac{f(i)x^{\underline{n+1}}}{(-1)^{n-i}i!(n-i)!(x-i)}\]我们要把函数平移\(m\)个单位长度,所以要写\(f(x+m)\)的式子,即\[f(x+m)=\sum_{i=0}^n\dfra......
  • 拉格朗日插值学习笔记
    拉格朗日插值第一步:子函数\(f_i(x)=\begin{cases}1&x=x_i\\0&x=x_j(i\nej)\end{cases}\)由此可得:\(f(x)=\sum\limits_{i=1}^ny_if_i(x)\)第二步:对于\(f_i(x)\),要满足当\(x=x_i\)时,\(y=1\),而\(x\nex_i\)时,\(y=0\)故:\(f_i(x)=\dfrac{\prod\limits_{j=1,j\......
  • 拉格朗日插值学习笔记
    拉格朗日插值定义给定一个多项式函数过点\((x_i,y_i)\),求出这个多项式函数的在\(x=k\)时的取值。公式\[f(k)=\sum_{i=0}^ny_i\prod_{j\not=i}\dfrac{k-x_j}{x_i-x_j}\]时间复杂度\(O(n^2)\)横坐标连续的拉格朗日插值在横坐标连续的情况下,可以做到\(O(n)\)插值。\[\b......
  • 拉格朗日乘子/拉格朗日乘数(Lagrange multiplier)
    基本的拉格朗日乘子法(又称为拉格朗日乘数法),就是求函数f(x1,x2,...)在g(x1,x2,...)=0的约束条件下的极值的方法。其主要思想是引入一个新的参数λ(即拉格朗日乘子),将约束条件函数与原函数联系到一起,使能配成与变量数量相等的等式方程,从而求出得到原函数极值的各个变量的解。 具体......
  • 拉格朗日插值法
    今天\(T2\)用到了,于是来学一学。拉格朗日插值法洛谷模板求值是指给定一个函数式,根据一个自变量求出因变量。而插值是给出一些自变量及其对应的因变量,求出符合的函数式。一种方法是将所有的值代入,然后解方程,显然极其不方便,这时,一位名为约瑟夫·路易斯·拉格朗日的人站了出来......
  • 拉格朗日插值
    拉格朗日插值普通拉格朗日插值众所周知,\(n+1\)个横坐标互不相同的点可以确定出唯一的最高次为\(n\)的多项式。当给定你\(n\)个点并要求你求出横坐标为\(x\)的点的纵坐标,高斯消元虽是个选择,但是\(O(n^3)\)的时间复杂度显然不优。于是我们选择用\(O(n^2)\)的拉格朗日......
  • 拉格朗日插值
    拉格朗日插值:给定\(n+1\)个点值\((x_i,y_i)\),对应唯一一个\(n\)次多项式,带入\(f(k)=\sum\limits_{i=1}^{n+1}y_i\prod\limits_{j\neqi}\frac{k-x_j}{x_i-x_j}\)。基本思想就是,构建\(n+1\)个多项式使得\(x=x_i\)时为1,\(x=x_j(j\neqi)\)时为0。当你取的点值连续......