拉格朗日插值法学习笔记
古人说过：(n + 1) 个点可以确定一个 (n) 次多项式。
然而通过解方程求出这个多项式显然不优雅；
(Lagrange) 插值法可以通过这 (n+1) 个点来求出多项式在 (x) 处的取值。
已知信息：(n + 1) 个点 ((x_i, y_i))；
所以要想办法构造出一个函数使得它过这些点；
考虑这样一个函数：
[l_i(x) = Pi_{i = 1,i
e j}^{n + 1}frac{x-x_j}{x_i-x_j}
]
可以发现函数 (l_i) 在 (x in {x_i}) 的取值有如下规律：
当 (x = x_i) 时，(l_i(x) = 1)；否则，(l_i(x) = 0)。这一点是显然的。
接着构造如下函数：
[f(x)=Sigma_{i = 1}^{n + 1}y_i imes l_i(x)
]
这样一来，函数 (f(x)) 就必过已知的 (n + 1) 个点。
按柿子直接算，时间复杂度：(O(n^2))
这大概就是我关于 (Lagrange) 插值法一些浅显的认识，下面是在 (OI) 中的应用。
重心拉格朗日插值
我们需要进行插值的次数可能会比较多，这时候上述做法可能并不能满足，需要一些优化。
我们观察函数
[f(x)=Sigma_{i = 1}^{n + 1}y_i imes l_i(x) \
l_i(x)=Pi_{i = 1,i
e j}^{n + 1}frac{x-x_j}{x_i-x_j}
]
可以发现 (l_i) 的分母是可以预处理的，复杂度 (O(n^2))；
其次，(l_i) 的分子在每次插值之前也可以处理：求出 (Pi_{i = 1,i
e j}^{n + 1}x - x_i)，把多的除掉。
预处理复杂度 (O(n^2))，单次计算复杂度 (O(n))，(可能会多一个逆元的(log))。
当 (x_i) 是一段整数区间时
那么 (l_i(x)) 中，分母就是 (fac_{i - 1} imes fac_{n - i}) ，在 (n - i) 为奇数时会有一个负号，(符号和边界问题看代码)；
同时，记：
[pre_i=Pi_{i = 0}^{i - 1} x - x_i \
suf_i=Pi_{i = i + 1}^{n + 1} x - x_i
]
那么：
[f(x) = Sigma_{i = 0}^{n + 1} y_i imes frac{pre_{i - 1}suf_{i + 1}}{fac_{i - 1}fac_{n - i}}
]
(待续，，， )