为方便书写,我们把点值序列用符号表示。

点值平移

给出(小于等于)次多项式个点值,求

考虑拉格朗日插值:

前面的下降幂可以预处理。后面是一个卷积的形式,可以求出。总时间复杂度

但是存在一个问题。如果,就会出现分母为的情况。这个可以细节处理。对于每个只会出现一次。因此我们定义一个函数,特别地,。这样就相当于把的贡献减掉了。然后我们枚举一遍,对于存在的情况,把贡献加上去即可(加贡献的时候要变换一下上面的式子,把为 0 的分母去掉就行)。

总时间复杂度仍为

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

阶乘计算

计算

。那么我们求出个点值即可求出答案。

不妨令。我们求出即可。

考虑倍增。假设我们求出了,如何求出

由于。问题转化为求出

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

那么设,那么有:,令,这样第一个问题就解决了。

对于第二个问题,我们拆成前后两半。以前半部分为例(两者只差一个常数)。我们要求。等价于。因此令即可。后半部分同理。

综上所述,我们可以在的时间内用求出

另外,用求出可以直接暴力。复杂度

该算法的总复杂度是

自然倒数幂和

计算

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

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

,设。那么有

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

注意到次的多项式,而我们要求的点值数是的。不妨令,得到

问题转化为求出

考虑倍增。问题转化为

  • 求出
  • 求出

由于,所以可以类似上一题一样做。

由于,所以结合一下的计算结果就可以了。

时间复杂度

参考文献

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

階乗 mod 素数 - min-25