拉格朗日插值

[Ir1d]

https://oi-wiki.org/math/numerical/lagrange/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛竞赛

[JimmyWang0417]

orz

[wqyzstql]

建议差分法讲的详细一点

[wqyzstql]

而且牛顿插值也可以在O(n^2)的复杂度内解决插值问题,建议介绍一下

[ghost]

@wqyzstql
建议差分法讲的详细一点

附议

[wcl95716]

差分法是说了一半么

[PeterlitsZo]

朋友们，问个问题，为啥有人用 %%% 来评论，这是啥意思嗷？

[Ir1d]

@PeterlitsZo 膜拜的意思（

[PeterlitsZo]

@PeterlitsZo 膜拜的意思（

为啥呢，是因为百分号 percent，所以 prprpr 吗（

[Ir1d]

@PeterlitsZo % => 模

[lliqa]

真好，从CRT的角度理解拉格朗日插值真是棒极了！

[qwq2519]

能补充x连续时候的O（n）做法吗

[Comrade-Commander]

CRT 合并的那一段，求 $m_i$ 逆元的时候，为什么上面是 $x-x_j$，下面变成了 $x_i-x_j$?

[onlypath]

@Comrade-Commander
CRT 合并的那一段，求 $m_i$ 逆元的时候，为什么上面是 $x-x_j$，下面变成了 $x_i-x_j$?

好像 $x-x_j$ 与 $x-x_j-(x-x_i)$ 在模多项式 $x-x_i$ 的意义下是等价的。然后就可以了吧？

[ultrapengqingli]

@wqyzstql
建议差分法讲的详细一点

附议

[Cat-shao]

差分法给我感觉就是牛顿差值。mathologer 发过一个视频挺好的：

Bilibili 链接1
Bilibili 链接2

（原视频发布于油管）

[SadPencil]

根据这里的代码写了一份Go语言的库，https://github.com/SadPencil/go-lagrange-interpolation
能求多项式系数的代码太少了，OI Wiki的这一份是写的最优雅的