组合数取模的一点整理0.0
随便整理一下吧。。。
现在我们要求$\binom{n}{m}\%p$，可能存在多种不同的要求。
（1）多次询问，$n\leq{10^3}$，$p$没有任何限制。
利用递推式$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$进行预处理，时间复杂度$O(n^2+q)$。
（2）多次询问，$n\leq{10^7}$，保证$p>n$且$p$是质数。
利用$\binom{n}{m}=\frac{n!}{m!(n-m)!}$。
直接预处理阶乘并利用费马小定理或者拓展欧几里得求逆元，时间复杂度$O(n+qlogn)$。
（3）单次询问，$n\leq{10^9}$，令$p=\prod{p_i^{q_i}}$，保证$max\{p_i^{q_i}\}\leq{10^5}$。
利用中国剩余定理对于每一个$p_i^{q_i}$单独考虑答案。
利用$\binom{n}{m}=\frac{n!}{m!(n-m)!}$，只需要计算阶乘以及阶乘的逆元即可。
注意在求逆元的时候，若是某部分是$p_i$的倍数则不存在逆元，所以我们将$p_i$单独提出计算。
利用$O(p_i^{q_i})$的时间预处理出$f_n=\prod_{j=1}^{n}j\%p_i^{q_i}[j\%p_i\not=0]$。
不妨定义$solve(n)$表示计算$n!\%p_i^{q_i}$的答案，我们可以利用递归$solve(n)=f_{n}\times{solve(\frac{n}{p_i})}$，并在这个过程中计算$p_i$的次数。
时间复杂度$O(max\{p_i^{q_i}\}logp)$。
（4）单次询问，$n\leq{10^5}，p\leq{10^9}$。
同样利用中国剩余定理，由于$n$很小，对于每一个$p_i^{q_i}O(n)$暴力预处理出$f_i$，并利用刚才的递归求解即可。
时间复杂度$O(nlogp)$。
（5）单次询问，$n,p\leq{10^9}$。
不妨考虑套用算法（3），不过直接利用$p_i^{q_i}$看起来并不能接受，我们考虑一点科技。
对于$q_i\geq{2}$，令$M=p_i^{\lceil\frac{q_i}{2}\rceil}$，考虑对于$1\leq{x}\leq{M}$且$x\%p_i\not=0$，我们需要计算一系列这样的东西：
$x\times{(M+x)}\times{(2M+x)}\times{(3M+x)}\times{...}$
我们不妨暴力展开观察一下。
$(x^2+Mx)\times{(2M+x)}\times{(3M+x)}\times{...}$
注意$Mx\times{2M}\equiv{0}\pmod{p_i^{q_i}}$，因为$p_i^{q_i}$显然整除$M^2$。
于是变成了$(x^3+(M+2M)x^2)\times{(3M+x)}\times{...}$
再变成$(x^4+(M+2M+3M)x^3)\times{...}$
所以我们直接利用快速幂+等差数列就能在$O(p_i^{\lceil\frac{q_i}{2}\rceil}logp_i)$时间里完成计算啦。
也需要用到刚才的递归计算，因此复杂度为$O(p_i^{\lceil\frac{q_i}{2}\rceil}logp_ilogn)。$
这一类所有质因子总时间复杂度最坏为$O(p^{\frac{2}{3}}logplogn)$。
对于$q_i=1$则不能够套用这种方法，我只会暴力。。。
具体来说可以参考这里：http://picks.logdown.com/posts/245545-binomial-coefficient-modulo-prime
但是这样丧心病狂真的好么。。。还是暴力大法好咯！
评论 (0)