阶乘取模
阶乘取模
给定素数$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)$