本文为个人学习笔记，所以阅读体验不能保证。

插值知识总览

前置知识：ntt,分治ntt,简单多项式知识

0.8级知识：差分使得未知多项式（系数连续）化为已知线性个组合数。时间，空间\(O(n^2)\)

1级知识：拉格朗日插值：多项式，单点\(O(n^2)\)求值，可线性动态插入维护。若给出的点横坐标连续（等差），可以线性。

2级知识：多项式多点求值

3级知识：多项式快速插值

差分插值：

给出\(f(1),f(2),f(3),...,f(n)\)，求\(f(x)\)

考虑差分之后可以化为一些组合数的和。

\(f(x)=x!\sum\limits_{i=0}^{n}f_i(-1)^ii!\sum\limits_{j=i}^{n}\frac{1}{(x-j)!(j-i)!}\)

拉格朗日插值

靠谱博客

多项式多点求值

多项式快速插值

【多项式】多项式插值相关_个人学习用

原文：https://www.cnblogs.com/czyarl/p/11842516.html