阶乘取模

Published: by Creative Commons Licence

  • Tags:

阶乘取模

给定素数$p$,以及某个数$0\leq n<p$,要求计算$n!$,其中$p\leq 10^9+7$。

讲两种做法,第一种时间复杂度为$O(\sqrt{n}(\log_2n)^2)$,第二种时间复杂度为$O(\sqrt{n}\log_2n)$。

我们记$f_d(x)=\prod_{i=1}^dx+i$。我们记$m=\lceil\sqrt{n}\rceil$,那么我们只需要计算出$f_m(0),f_m(m),\ldots,f_m((m-1)m)$,并将它们乘起来,缺失的部分最多$O(m)$项,我们暴力处理即可。

那么怎么计算$f_m(km)$呢,其中$0\leq k<m$。我们可以发现$f_m$是一个$m$阶的多项式,我们可以先求出通过分治+FFT以$O(m(\log_2m)^2)$时间复杂度快速求出多项式,之后利用多点求值的技术$O(m(\log_2m)^2)$的时间复杂度内求出这$m$个值。

但是众所周知,这个多点求值的算法常数是真的大,假如你真的用这个方法,那很有可能会TLE的。下面我们提第二种方法。

我们考虑倍增的方法,假设我们已知:$f_d(ks)$,其中$0\leq k\leq d$。下面我们考虑怎么计算$f_{d+1}(ks)$以及$f_{2d}(ks)$。

可以发现$f_{d+1}(ks)=f_d(ks)\cdot (ks+d+1)$,而对于$f_{d+1}((d+1)s)$,我们可以直接暴力计算,时间复杂度最多$O(\sqrt{n})$。

而对于$f_{2d}(ks)$,我们可以通过$f_{2d}(ks)=f_d(ks)f_d(ks+d)$求解。右边项我们需要的是

  • $f_d(ks),0\leq k\leq 2d$
  • $f_d(ks+d),0\leq k\leq 2d$

记$g(x)=f_d(xs)$,可以发现问题实际上是给定了$g(0),\ldots,g(d)$,要求插值出$g(k+\delta)$,其中$0\leq k\leq d$。考虑通过拉格朗日插值法求解$g$。

由于我们仅利用上面公式求解未知的量,因此一定有$x\neq i$。我们可以做下面变换:

下面我们考虑如何计算$g(t)$,其中左边的项可以通过$O(d)$时间复杂度预处理阶乘,之后每个请求$O(1)$处理。而对于右边的部分,可以发现它可以描述为两个多项式的卷积,我们提前通过FFT处理出卷积的结果即可,预处理的时间复杂度为$O(d\log_2d)$,回答单个请求的时间复杂度为$O(1)$。

这里提一下上面出现了比较多的$x-i$,我们可以保证它不可能是$0$。因为我们可以保证所有要求的$g(k+\delta)$都是未知量,即和${0,1,\ldots,d}$无交集。

上面的过程总的时间复杂度为$O(1\log_21+2\log_22+\ldots+m\log_2m)=O(m\log_2m)=O(\sqrt{n}\log_2n)$

参考资料