我猜我只学习了比较简单的一部分……
# 插值法
根据多项式函数的基本知识,我们知道平面上任意横坐标不同的 $n$ 个点,可以确定一个次数为 $n-1$ 的函数曲线。
插值法则是在给定这 $n$ 个点的情况下计算函数曲线的表达式。
这一点类似于拟合,只不过插值要求经过每一个点,而拟合只需要使每个点大致趋近于曲线即可。
拉格朗日插值法是众多插值法中比较简单的一个。
# 算法内容
记给出的点为 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$,要计算出一个次数为 $n-1$(项数为 $n$)的一个函数 $F(x)$。
拉格朗日插值法的原理是:把 $F(x)$ 表示成 $n$ 个易于计算的曲线之和,即
于是可以这样构造 $F_i(x)$ —— $F_i(x)$ 在 $x_i$ 处取值为 $y_i$,在 $x_j$($j\neq i$)处取值为 $0$,根据这个思路构造出的 $F_i(x)$ 如下:
易于证明上式在 $x_i$ 处取 $y_i$,在 $x_j$($j\neq i$)处取 $0$。
# 模板
> 洛谷 P4781
1 | /*Lucky_Glass*/ |
# 优化DP
这样一个计算多项式的算法如何优化DP?
实际上,这要求DP值的计算方式是一个多项式。当我们代入该多项式的自变量非常的大时,我们不能直接去DP计算这个值;但是如果我们可以证明这个多项式的次数比较小(比如为 $n$),就能够只计算出在这个多项式中的 $n$ 个点($n$ 个DP值),再用拉格朗日插值法求出多项式,代入自变量求解即可。
- 【例题】calc「集训队互测」
> 洛谷 P4463
解析:
因为是要选出 $n$ 个不同的数,我们就可以先不考虑这些数的顺序,只是选出这些数再全排一下就好了。
先写出一个非常暴力的DP,即 $f_{i,j}$ 表示在 $[1,j]$ 的数中选了 $i$ 个数,这些数的积之和:
然后我们假设当 $i$ 固定时 $f_{i,j}$ 是一个关于 $j$ 的多项式 $F_i(j)$,考虑利用数学归纳法证明:
- 当 $i=0$ 时,$F_i(j)$ 是常数多项式;
- 当 $i>0$ 时,由递推式可得,因多项式的和、积均为多项式,所以 $F_i(j)$ 为多项式。
> Hint. 若 $F(x)$ 是一个 $n$ 次多项式,则 $F(x)-F(x-1)$ 是一个 $n-1$ 次多项式。
再计算 $F_i(j)$ 的次数,设为 $h(i)$。根据递推式,可得
而 $h(0)=0$,则 $h(n)=2n$。也即 $F_n(j)$ 是一个 $2n$ 次多项式,需要确定 $2n+1$ 个点。于是只需要算出 $f_{i,k}$($k\in[1,2n+1]$)就可以得到 $F_n(j)$,最后把 $j=k$ 代入就可以得到答案了。