组合数取模

2019-04-13 20:33发布

站内文章 / 模拟电子
10153 0 1045
赤裸裸的组合数取模没什么意思，但也是必须掌握的一门知识。一个计数的问题辛辛苦苦搞到最后发现被取模坑成狗也是很有可能的。今天主要总结一下各类取模问题。限长整(long)范围内。 所谓组合数取模，即求Cmn % p
  1. 1<=m<=n<=1e3,1<=p<=long 杨辉三角，直接递推 Cmn=Cmn−1+Cm−1n−1
  2. 1<=m<=n<=1e6,1<=p<=long,n<p,p∈primes 直接逆元，预处理出n!及其逆元即可。由费马小定理，对于(a,p)=1,则，a−1=ap−2
  3. 1<=m<=n<=long,1<=p<=long,p∈primesLucas定理。即令
    n=n0+n1p+n2p2+⋯+nkpk,0<=ni<p
    m=m0+m1p+m2p2+⋯+mkpk,0<=mi<p
    则有:
    Cmnmodp=∏i=0kCminimodp
    若存在ni<mi，则Cmnmodp=0
  4. 1<=m<=n<=1e6,1<=p<=long没错，将Cmn质因数分解，然后求模。具体是
    • 分别将n!,m!,(n−m)!分解掉，然后指数相减得到最终的质因数分解。
    • 对每个质因数，快速幂取模

  5. 1<=m<=n<=long,1<=p<=1e6由于p可以是合数，所以前面无论逆元还是Lucas都解决不了。
    将前面几种方法结合一下。
    • 将p质因数分解p=∏ki=0paii

热门文章