求组合数的O(n^2)和O(n)解法及模板

概率论中的组合数应该比较熟悉吧，在数论中组合数也具有重大意义，下面介绍组合数的解法：

方法一O(n^2)：

利用公式(n,m)=(n-1,m-1)+(n-1,m)：

模板：

#include<cstdio>

const int N =  + ;

const int MOD = (int)1e9 + ;

int comb[N][N];//comb[n][m]就是C(n,m)

void init(){

    for(int i = ; i < N; i ++){

        comb[i][] = comb[i][i] = ;

        for(int j = ; j < i; j ++){

            comb[i][j] = comb[i-][j] + comb[i-][j-];

            comb[i][j] %= MOD;

        }

    }

}

int main(){

    init();

}

方法二(O(n))：

因为大部分题都有求余，所以我们大可利用逆元的原理（没求余的题目，其实你也可以把MOD自己开的大一点，这样一样可以用逆元做）。利用公式：

我们需要求阶乘和逆元阶乘。

模板：

const int MOD = (int)1e9 + ;

int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘

void init(){

    inv[] = ;

    for(int i = ; i < N; i ++){

        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;

    }

    F[] = Finv[] = ;

    for(int i = ; i < N; i ++){

        F[i] = F[i-] * 1ll * i % MOD;

        Finv[i] = Finv[i-] * 1ll * inv[i] % MOD;

    }

}

int comb(int n, int m){//comb(n, m)就是C(n, m)

    if(m <  || m > n) return ;

    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;

}

int main(){

    init();

}

巴特西

求组合数的O(n^2)和O(n)解法及模板

最新文章

热门文章