点值平移与倍增求值学习笔记

为方便书写，我们把点值序列$f(x_1),f(x_2),\cdots,f(x_m)$用符号$f(x_1,x_2,\cdots,x_m)$表示。

点值平移

给出（小于等于）$k$次多项式$h(x)$的$k+1$个点值$h(0,1,\cdots,k)$，求$h(d,1+d,\cdots,k+d)$。

考虑拉格朗日插值：

$$\begin{aligned} h(x+d) &=\sum_{i=0}^kh(i)\prod_{j\ne i}\frac{x+d-j}{i-j} \\ &=(x+d)^{\underline{k+1}}\sum_{i=0}^k\frac{1}{x+d-i} \frac{h(i)(-1)^{k-i}}{i!(k-i)!} \\ \end{aligned}$$

前面的下降幂可以$O(k)$预处理。后面是一个卷积的形式，可以$O(k\log_2k)$求出。总时间复杂度$O(k\log_2k)$。

但是存在一个问题。如果$x+d-i=0$，就会出现分母为$0$的情况。这个可以细节处理。对于每个$x$，$x+d-i=0$只会出现一次。因此我们定义一个函数$t(i)=\frac{1}{i}\;(i>0)$，特别地，$t(0)=0$。这样就相当于把$x+d-i$的贡献减掉了。然后我们枚举一遍$x$，对于存在$x+d-i=0$的情况，把贡献加上去即可（加贡献的时候要变换一下上面的式子，把为 0 的分母去掉就行）。

总时间复杂度仍为$O(k\log_2k)$。

接下来我们来看一下点值平移算法的应用。

阶乘计算

计算$n!\bmod p$。

$n<p$。

设$f_T(x)=\prod_{i=1}^{T}(x+i)$。那么我们求出$f_T(x)$的$\frac{n}{T}$个点值即可求出答案。

不妨令$T=\lfloor\sqrt{n}\rfloor$。我们求出$f_T(0,T,2T,\cdots,T^2)$即可。

考虑倍增。假设我们求出了$f_k(0,T,2T,\cdots,kT)$，如何求出$f_{2k}(0,T,2T,\cdots,2kT)$？

由于$f_{2k}(x)=f_k(x)f_k(x+k)$。问题转化为求出

• $f_k(kT+T,kT+2T,\cdots,2kT)$。
• $f_k(k,T+k,2T+k,\cdots,2kT+k)$。

这两个问题可以转化为点值平移问题。

那么设$h(x)=f_k(Tx)$，那么有：$f_k(0,T,\cdots,kT)=h(0,1,\cdots,k)$，$f_k(kT+T,kT+2T,\cdots,2kT,2kT+T)=h(k+1,\cdots,2k+1)$，令$d=k+1$，这样第一个问题就解决了。

对于第二个问题，我们拆成前后两半。以前半部分为例（两者只差一个常数）。我们要求$f_k(k,T+k,\cdots,kT+k)$。等价于$h(\frac{k}{T},1+\frac{k}{T},\cdots,k+\frac{k}{T})$。因此令$d=\frac{k}{T}$即可。后半部分同理。

综上所述，我们可以在$O(k\log_2k)$的时间内用$f_k(0,T,\cdots,kT)$求出$f_{2k}(0,T,\cdots,2kT)$。

另外，用$f_k(0,T,2T,\cdots,kT)$求出$f_{k+1}(0,T,2T,\cdots,kT,(k+1)T)$可以直接暴力。复杂度$O(k)$。

该算法的总复杂度是$O(T\log_2T)$。

自然倒数幂和

计算$\sum_{i=1}^ni^{-k} \bmod p$。

$k>0$。

首先这并不是一个容易处理的多项式函数。因此我们需要做一些转化：

$$\sum_{i}\frac{1}{i^k} = \sum_{i}\frac{\prod_{j\ne i}j^k}{\prod_j j^k} =\frac{\sum_i\prod_{j\ne i}j^k}{\prod_j j^k}$$

分子分母都是多项式。因此我们分别求出两者在$x=n$处的点值即可。

设$f_T(x)=\prod_{i=1}^{T}(x+i)^k$，设$g_T(x)=\sum_{i=1}^T\frac{f_T(x)}{(x+i)^k}$。那么有$\frac{g_T(x)}{f_T(x)}=\sum_{i=1}^T(x+i)^{-k}$。

因此我们只需要对$f_T,g_T$分别做多点求值即可。

注意到$f_T,g_T$是$Tk$次的多项式，而我们要求的点值数是$\frac{n}{T}$的。不妨令$Tk=\frac{n}{T}$，得到$T=\sqrt{\frac{n}{k}}$。

问题转化为求出$f_T(0,T,\cdots,T^2)$和$g_T(0,T,\cdots,T^2)$。

考虑倍增。问题转化为

• 用$f_k(0,T,\cdots,kT)$求出$f_{2k}(0,T,\cdots,2kT)$。
• 用$g_k(0,T,\cdots,kT)$求出$g_{2k}(0,T,\cdots,2kT)$。

由于$f_{2k}(x)=f_k(x)f_k(x+k)$，所以可以类似上一题一样做。

由于$g_{2k}(x)=g_k(x)f_k(x+k)+f_k(x)g_k(x+k)$，所以结合一下$f_k$的计算结果就可以了。

时间复杂度$O(T\log_2T)$。

参考文献

「翻译向」阶乘模大质数 - ZZQ’s Blog

階乗 mod 素数 - min-25