欢迎大家去看杜瑜皓@《多项式及求和》

多项式线性插值算法讲的是：

已知一个 $k$ 次多项式 $F(x)$ 在整点 $0,1,2,3,4,5,…,k$ 处的值为 $F(0),F(1),F(2),…,F(k)$
我们能够在 $O(k)$ 的时间内求出 $F(n)$ 或者在 $O(k \log k）$ 的时间内求出原多项式$F(x)$

二项式反演

欢迎大家去看我的博客《二项式反演》啊orz

简单来说就是我们发现如果数列 $\{f_n\}$ 和 $\{g_n\}$ 满足:

$g_n=\sum_{i=0}^n C_n^i f_i$

则：

$f_n=\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$

牛顿级数

我们发现 $C_x^0,C_x^1,C_x^2,…,C_x^k$ 次数两两不同，他们线性无关，于是我们设：

$F(x)=\sum_{i=0}^k C_x^i p_i$

由二项式反演就可以得到：

$p_n=\sum_{i=0}^n (-1)^{n-i}C_n^iF(i)$ $\frac{p_n}{n!}=\sum_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\frac{F(i)}{i!}$

显然我们可以通过FFT在 $O(k \log k)$ 时间内算出各项系数 $p_i$ 。

FFT？

我们真的需要使用FFT来求 $F(n)$ 吗？

对于 $x > k$ 的 $F(x)$，有：

$F(x)=\sum_{i=0}^k C_x^i p_i$ $=\sum_{i=0}^k C_x^i \sum_{j=0}^i (-1)^{i-j}C_i^jF(j)$ $=\sum_{i=0}^k \sum_{j=0}^i F(j) (-1)^{i-j}C_x^iC_i^j$ $=\sum_{j=0}^k F(j) \sum_{i=j}^k (-1)^{i-j}C_x^jC_{n-j}^{i-j}$ $=\sum_{j=0}^k C_x^j F(j) \sum_{i=j}^k(-1)^{i-j}C_{n-j}^{i-j}$ $=\sum_{j=0}^k C_x^j F(j) (-1)^{k-j}C_{n-j-1}^{k-j}$ $=\sum_{j=0}^k (-1)^{k-j} F(j) \frac{x!(x-j-1)!}{j!(x-j)!(k-j)!(x-k-1)!}$ $=\sum_{j=0}^k (-1)^{k-j} F(j) \frac{x(x-1)(x-2)...(x-k)}{(x-j)j!(k-j)!}$

这样我们就可以在知道 $F(0),F(1),…,F(k)$ 的情况下，在 $O(k)$ 时间内求出 $F(n)$。

二项式反演？

如果你会多项式插值的话就知道，这其实就是拉格朗日插值。

拉格朗日插值法

如果我们有 $F(x_1)=y_1,F(x_2)=y_2,…,F(x_n)=y_n$，则拉格朗日插值多项式等于
$F(x)=\sum_{i=1}^n y_i \prod_{j=1,j \neq i}^n \frac{x-x_j}{x_i-x_j}$

我们尝试带入 $0,1,2,…,k$ 和 $F(0),F(1),…,F(k)$ :

$F(x)=\sum_{i=0}^k F(i) \prod_{j=0,j \neq i}^k \frac{x-j}{i-j}$ $=\sum_{i=0}^k F(i) \frac{x(x-1)(x-2)...(x-k)}{(x-i)(i-0)(i-1)...\times 1 \times (-1) \times (-2) \times ...\times (i-k)}$ $=\sum_{i=0}^k F(i) \frac{x(x-1)(x-2)...(x-k)}{(x-i) i! (-1)^{k-i}(k-i)!}$ $=\sum_{i=0}^k (-1)^{k-i} F(i) \frac{x(x-1)(x-2)...(x-k)}{(x-i) i! (k-i)!}$

大功告成！

例: 自然数幂和

已知 $k \leq 2 \times 10^5,n \leq 10^{10000},p \leq 10^{18}$ 且 $p$ 为质数。
求 $\sum_{i=0}^n i^k$ 对 $p$ 取模的结果。

分析

我们记 $F(x)=\sum_{i=0}^x i^k,x \in \mathbb{N}$ 。首先我们需要知道 $F(x)$ 是一个 $k+1$ 次多项式。只需求出$F(0),F(1),…,F(k+1)$ 就可以使用上面讲的线性插值求出 $F(n)$ 啦orz

求$F(0),F(1),..,F(k+1)$ 的话注意到 $i^k$ 是完全积性函数，可以用欧拉筛法在线性时间内求出 $0^k,1^k,…,(k+1)^k$，问题完美解决。

对了，你可以尝试挑战一下 BZOJ-4126. 国王奇遇记加强版之再加强版。体验一下线性插值带来的快感。