拉格朗日插值 & 线性递推
拉格朗日插值
动态拉格朗日插值
插值公式（$n$ 个点 $x_i,y_i$ 确定一个 $n-1$ 次多项式，求出点 $x$ 处的取值）：
$$
f(x) = \sum_{i=1}^n y_i \prod_{j \ne i} \frac{x-x_j}{x_i-x_j}
$$
这个插值公式显然是 $O(n^2)$ 的，但是它可以动态向集合中加入点，动态询问当前多项式的点值。
也就是用前后缀积优化一下就可以了，此处给出代码：
1 |
|
快速拉格朗日插值
这个方法只适用于静态的 $n$ 个点，不支持加点，然后询问多个点的点值，并且或者让你求出系数。
我们这里只讲求出系数，因为询问多个点的点值也很简单，把 $x$ 展开之后用多项式多点求值即可，或者求出系数之后多项式多点求值。
如何求出系数？我们回到公式：
$$
f(x) = \sum_{i=1}^n y_i \prod_{j \ne i} \frac{x-x_j}{x_i-x_j}
$$
首先求出常数项：
$$
f(x) = \sum_{i=1}^n y_i \prod_{j \ne i} \frac{1}{x_i-x_j}
$$
这个怎么做？相当于对于多项式 $A=\prod_{i=1}^n \frac 1{x-x_i}$ 求出 $x$ 在等于 $x_{1 \sim n}$ 处的点值然后乘上 $x_i-x_i=0$。
因为这两个值都是 $0$，考虑运用洛必达法则，也就是 $x$ 在等于 $x_{1 \sim n}$ 处的点值然后乘上 $x_i-x_i=0$ 就等于 $x$ 在多项式 $A=\prod_{i=1}^n \frac 1{x-x_i}$ 求导之后的点值。
这一部分用多项式多点求值即可。
设只用 $x_{l \sim r}$ 算出来 $f_{l,r}$（是一个多项式），就是 $\sum_{i=l}^r y_iA’(x_i) \prod_{l \le j \le r,j \ne i} (x-x_j)$，然后考虑分治合并。
首先 $f_{l,l}$ 可以很简单地得到是 $y_iA’(x_i)$，然后我们考虑合并 $f_{l,mid}$ 和 $f_{mid+1,r}$：
$$
\begin{aligned}
f_{l,r}&= \sum_{i=l}^r y_iA’(x_i) \prod_{l \le j \le r,j \ne i} (x-x_j) \\
&= \sum_{i=l}^{mid} y_iA’(x_i) \prod_{l \le j \le r,j \ne i} (x-x_j) +\sum_{i=mid+1}^{r} y_iA’(x_i) \prod_{l \le j \le r,j \ne i} (x-x_j) \\
&= \sum_{i=l}^{mid} y_iA’(x_i) \prod_{l \le j \le mid,j \ne i} (x-x_j) \prod_{mid+1 \le j \le r}(x-x_j) +\sum_{i=mid+1}^{r} y_iA’(x_i) \prod_{mid+1 \le j \le r,j \ne i} (x-x_j) \prod_{l \le j \le mid}(x-x_j) \\
&= f_{l,mid}g_{mid+1,r} + f_{mid+1,r}g_{l,mid} \\
\end{aligned}
$$
其中 $g_{l,r} = \prod_{i=l}^r(x-x_i)$，然后用分治下去的 NTT 计算就可以了。
最后的答案就是 $f_{1,n}$，代码实现如下，时间复杂度 $O(n \log^2 n)$。
1 |
|
常系数齐次线性递推
我们要解决的是 $a_i=\sum_{j=1}^k a_{i-j}b_j$，在 $O(k \log k \log n)$ 的时间复杂度内求出 $a_n$ 的值。
我们以 Fib 数列为例，$f_1=1,f_2=1,f_3=2$，因为 $f_i=f_{i-1}+f_{i-2}$，我们把 $f_1$ 和 $f_2$ 看作未知数，那么有：
$$
\begin{aligned}
f_3 &= f_1+f_2 \\
f_4 &= f_3+f_2=f_1+2f_2 \\
f_5 &= f_3+f_4=2f_1+3f_2 \\
\end{aligned}
$$
如果令 $f_1=x^1,f_2=x^2$，那么就有：
$$
\begin{aligned}
f_3 &= x^1+x^2 \\
f_4 &= f_3+f_2=x+2x^2 \\
f_5 &= f_3+f_4=2x^1+3x^2 \\
\end{aligned}
$$
如果我们让项数从 $0$ 开始，那么 $x^2=x^0+x^1$，所以 $f_5=3x^0+5x^1$，容易发现这就是 $x^5$ 对 $x^2-x^0-x^1$ 取模之后的结果。
并且 $x^2-x^0-x^1=0$ 是这个斐波那契数列的特征公式，于是问题转化为了求 $x^n$ 对这个递推式的特征公式取模后的结果，设其为 $A=a_0x^0+a_1x^1+\dots+a_{k-1}x^{k-1}$，因为我们知道 $x^{0 \sim k-1}$ 的值，所以直接带入计算即可。
考虑如何求出取模后的值，我们用倍增快速幂的方法即可，也就是先求出 $x^i \bmod T$ 的值，然后平方一下再取模就是 $x^{2i} \bmod T$ 的值，最后按照倍增快速幂合并出 $x^n \bmod T$ 就可以了。（$T$ 是特征多项式）
时间复杂度分析：每次乘法取模次数都是 $O(k)$ 级别的，一共乘+模 $O(\log n)$ 次，所以时间复杂度就是 $O(k \log k \log n)$。
代码实现（P4723 【模板】常系数齐次线性递推）：
1 |
|