组合数的几种求法

大家好，欢迎来到IT知识分享网。

前言

在很多算法的应用中，组合数常常作为一个重要的组成部分，想要计算出组合数也有许多算法，那么，该如何在合适的地方使用合适的算法呢？

一、组合数的定义

公式：$C_a^b$ $=$ $a!/(b!)\ast (b-a)!$
时间复杂度：$O(b)$
说明：一般在$a$较大且$b$较小时使用，代码较为简单易懂，可以搭配逆元使用。
代码(逆元为费马小定理)：

ll C(ll a,ll b){ 
    ll up = 1,down = 1; for(int i = a,j = 1;j<=b;--i,++j){ 
    up = up * i % p; down = down * j % p; } return up * qmi(down,p-2); } 

二、杨辉三角

公式：$C_a^b$ $=$ $C_{a-1}^b$ $+$ $C_{a-1}^{b-1}$
时间复杂度：$O(a^2)$
说明：前提为$a$比较小，可以在询问条目很大时用作离线打表节约时间。
代码：

ll C(ll a,ll b){ 
    for(int i=0;i<=a;++i){ 
    for(int j=0;j<=b&&j<=i;++j){ 
    if(!j) c[i][j] = 1; else c[i][j] = c[i-1][j] + c[i-1][j-1]; } } return c[a][b]; } 

三、Lucas定理

公式：$lucas(a,b)$ $=$ $lucas(a/p,b/p)$ $\ast$ $C_{a\%p}^{b\%p}$
时间复杂度：$O(lo{g}_p^n\ast p)$
说明：用于以较快的速度计算很大的组合数，通常要配合阶乘打表食用。
代码：

ll fact[N],infact[N]; void get_fact(){ 
    fact[0] = infact[0] = 1; for(int i=1;i<N;++i){ 
    fact[i] = fact[i-1]*i%p; infact[i] = infact[i-1]*qmi(i,p-2)%p; } } ll C(ll a,ll b){ 
    if(a<b) return 0; return fact[a]*infact[a-b]*infact[b]%p; } ll lucas(ll a,ll b){ 
    if(a<p&&b<p) return C(a,b); return lucas(a/p,b/p)*C(a%p,b%p)%p; } 

四、分解质因数

方法：获取结果的所有质因数的次数，并以快速幂求解
时间复杂度：$O(logaloga)$
说明：用于以较快的速度计算很大的组合数，模数不为质数也没有关系，但代码量和前几种相比较多。
代码：

int prime[M],cnt; bool st[M]; int n,p; void init(int n){ 
    for(int i=2;i<=n;++i){ 
    if(!st[i]) prime[cnt++] = i; for(int j=0;prime[j]*i<=n&&j<cnt;j++){ 
    st[prime[j]*i] = true; if(i%prime[j]==0) break; } } } ll qmi(ll a,ll b){ 
    ll res = 1; while(b){ 
    if(b&1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } ll get(ll b,ll a){ 
    ll s = 0; while(b) s += b/a , b = b/a; return s; } ll C(ll a,ll b){ 
    if(a<b) return 0; ll res = 1; for(int i=0;i<cnt;++i){ 
    ll pr = prime[i]; //a!/b!/(a-b)! ll s = get(a,pr) - get(b,pr) - get(a-b,pr); res = res * qmi(pr,s) % p; } return res; } 

总结

本文仅仅讲了求组合数的各种方法，在算法中具体要用到哪种，或者要以怎样的形式使用还需另加思考。