考虑这样一个问题：给出非负整数$n,m$和正整数$p$，分别求${n\choose m}\bmod p$。
在许多题目中都要解决这样的问题。
这片博客主要讨论的就是解决该问题的一些算法。
首先来看看$n\choose m$是什么东西。
这是组合数，表示从$n$个互不相同的物品中取出$m$个物品的方案数。
它也叫二项式系数，因为它是$n$次二项式展开后第$m$项的系数。
下面给出组合数的一些基本性质。
递推式：$\large{{n\choose m}={n-1\choose m-1}+{n-1\choose m}}$
通项式：$\large{{n\choose m}=\frac{n!}{m!\left(n-m\right)!}}$
$${n\choose m}={n\choose n-m}$$
$${n\choose m}=\frac{n}{m}{n-1\choose m-1}$$
$${n\choose m}=\frac{n}{n-m}{n-1\choose m}$$
$$\sum_{i=0}^n {n\choose i}=2^n$$
$$\sum_{i=1}^n i={n+1\choose 2}$$
这些性质大多都是“显然的”，剩下的也可以通过这些显然的性质推导出来，就不再说明。
现在回到问题上来。下面是针对不同数据的一些算法。渐进记号中用$Q$表示询问组数。
- 直接通过递推式进行DP，时间复杂度$\mathcal{O}\left(Qnm\right)$。
- （$p$是质数）通过通项式计算，对于单组询问$\mathcal{O}\left(p\right)$，对于多组询问则可以预处理阶乘和阶乘逆元（很显然有$\left(n!\right)^{-1}\equiv\left(\left(n+1\right)!\right)^{-1}\left(n+1\right)\pmod p$），做到$\mathcal{O}\left(p+Q\right)$的复杂度。
- （$p$是质数）卢卡斯定理，即对于非负整数$n,m$和质数$p$，有${n\choose m}\equiv{n\bmod p\choose m\bmod p}\times{\left\lfloor n/p\right\rfloor\choose\left\lfloor m/p\right\rfloor}\pmod p$。所以只须用上一个方法计算后一项，前一项递归求解。时间复杂度不会算。
- （$p=\prod_\limits{i=0}^\limits{k-1}p_i$（$p_i$为互不相同的质数））将$p$分分解质因数，分别计算结果（用上面几个方法之一），用中国剩余定理合并。设$f\left(n,m,p\right)$为计算${n\choose m}\bmod p$（$p$为质数）的复杂度，则这个算法的复杂度为$\mathcal{O}\left(Q\left(k+\sum\limits_{i=0}^{k-1}f\left(n,m,p_i\right)\right)\right)$。
-
（$p=a^c$（$a$为质数））因为这个个人感觉比较难以理解，就用一个例子来说明。假设现在要计算${30\choose 20}\bmod 3^2$。
使用通项式计算：$\frac{30!}{20!10!}\bmod 3^2$。看起来很对的样子，然而因为分母不与$9$互质，不能计算逆元。
单独考虑计算阶乘（以$20!$为例）。$20!$不与$3^2$互质是因为其中有一些$3$的倍数：$3,6,9,12,15,18$。那么把他们单独拿出来，并提出$3$这个因数，得到$\small{\left(1\times 3\right)\times\left(2\times 3\right)\times\left(3\times 3\right)\times\left(4\times 3\right)\times\left(5\times 3\right)\times\left(6\times 3\right)=6!\times 3^6}$。显然$6!$可以递归计算再乘进去，而$3^6$待会儿再说。
$20!$提出$3$的倍数后剩下的部分有点奇怪，不是很好算的样子。但是因为要模$9$，所以这个部分其实是循环的，也就是说实际上是计算$\small{\left(1\times 2\times 4\times 5\times 7\times 8\right)^2\times 1\times 2}$，所以只要计算前面一段，剩下的快速幂，最后乘上多出来的不在循环中的一小部分即可。
这样处理后$20!\bmod 9$就变成了$x\times 3^y$的形式。那么对$10!$和$30!$也这么处理，就可以使整个通项式的分子和分母也变成这样的形式，即$\large{\frac{x_1\times 3^{y_1}}{x_2\times 3^{y_2}}}$。$x_2$因为已经没有了因数$3$所以直接逆元。$3^{y_2}$看起来很难对付的样子，但实际上它与$3^{y_1}$约分可以直接约掉（一定全部约掉了，否则算出来就不是整数了，而组合数显然一定是整数）。
时间复杂度不会算。 -
（$p$为任意数）设$p=\prod_\limits{i=0}^\limits{k-1}p_i^{c_i}$，那么对于每个$p_i^{c_i}$分别用上个方法计算，最后用中国剩余定理合并。
至于时间复杂度，一样不会算。
于是是时候放代码了！
评论 (0)
