阶乘取模

Published: June 26, 2020 by Daltao

Categories:
algorithm 101

阶乘取模
参考资料

阶乘取模

给定素数 $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$ 。

$\begin{aligned} g(x)&=\sum_{i=0}^dg(i)\prod_{j=0,j\neq i}^d\frac{x-j}{i-j} \end{aligned}$

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

$\begin{aligned} &=\sum_{i=0}^dg(i)\frac{\prod_{j=0}^dx-j}{(x-i)\prod_{j\neq i}i-j}\\ &=[\prod_{j=0}^dx-j][\sum_{i=0}^d\frac{1}{(x-i)}\frac{g(i)}{\prod_{j=0,j\neq i}^di-j}]\\ \end{aligned}$

下面我们考虑如何计算 $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)$

阶乘取模

参考资料