BSGS的严格根号算法
Latex在windows以及mac上的中文解决方案,以及一些小技巧

组合数取模的一点整理0.0

shinbokuow posted @ Sep 16, 2015 10:56:01 AM in Something with tags 组合数取模 数学 , 732 阅读

 

随便整理一下吧。。。
现在我们要求$\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
但是这样丧心病狂真的好么。。。还是暴力大法好咯!

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter