用 C++ 求组合数的两种方法

📝 文章摘要

GLM-4

什么是组合数？

组合数是组合数学中的基本概念，用符号 $C(n, m)$ 或 $\binom{n}{m}$ 表示，指从 $n$ 个不同元素中不计顺序地选取 $m$ 个元素的所有可能方案数，其计算公式为 $C(n, m) = \frac{n!}{m!(n-m)!}$ ，其中 $n!$ 表示阶乘运算。例如从 5 个学生中选出 2 人参加比赛，不同的选择方案数就是组合数 $C(5, 2) = 10$ 。

杨辉三角

利用杨辉三角的性质：

C(n,m)=C(n−1,m−1)+C(n−1,m)C(n,m)=C(n−1,m−1)+C(n−1,m)

通过动态规划预先计算所有组合数。

  
#include <iostream>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init()
{
    for(int i = 0; i < N; i ++ )
        for(int j = 0; j <= i; j ++ )
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
int main()
{
    init();
    int n;
    scanf("%d", &n);
    while(n --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}

乘法逆元

当需要计算组合数模 $p$ （通常 $p$ 为质数）时，使用费马小定理：

a^{p-1} \equiv 1 \pmod{p} \Rightarrow a^{-1} \equiv a^{p-2} \pmod{p}

组合数公式：

C(n, m) = \frac{n!}{m!(n-m)!} \mod p

  
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fact[N],infact[N];
LL qmi(LL a,int k,int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}
int main()
{
    //预处理阶乘和阶乘的逆元
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i ++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod; //这里是关键，把组合数的公式转化为乘法形式
    }

    int n;
    scanf("%d",&n);
    while(n --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%lld\n", (LL)fact[a] * infact[a - b] % mod * infact[b] % mod);
        //因为3个1e9级别的数相乘会爆longlong，所以乘了两个后要mod一下1e9+7，不影响结果
    }
    return 0;
}

本文由 AirTouch 编写，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。