快速回忆拉格朗日插值法

· · 个人记录

n+1$ 个点确定一个 $n$ 次多项式 $f(x) f(k)=∑_{i=0}^ny_i∏_{i≠j}\frac{k-x_j}{x_i-x_j}

连续的 n+1 个点求 f(k)

l_i=∏_{j=0}^i(k-j)=(k-i)l_{i-1}\\ r_i=∏_{j=i}^n(k-j)=(k-i)r_{i+1}\\ res_i=(-1)^{n+1-i}y_i\frac{l_{i-1}⋅r_{i+1}}{(i-1)!⋅(n+1-i)!}\\ f(k)=∑_{i=0}^nres_i