C++中求组合数的各种方法总结详解

前言

组合数问题在许多算法问题中都有广泛应用，在C++中求组合数的方法也多种多样。本文将总结并详细解释C++中求组合数的各种方法。

直接递推法

组合数的定义式为：$C_{n}^{m}=\frac{n!}{m!(n-m)!}$，可以通过递归的方法直接求解。

递归式为：$C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}$

具体实现代码如下：

int C(int n, int m)
{
    if (m == 0 || n == m)
        return 1;
    else
        return C(n - 1, m - 1) + C(n - 1, m);
}

该方法简单易懂，但运行时间可能比较长，特别是当n和m较大时，时间复杂度为O($2^n$)。

非递归的递推法

通过分析递推公式，我们可以发现$C_{n}^{m}$只与$C_{n-1}^{i}(i\leq m)$有关。

所以可以通过非递归的方法提高运算速度。

具体实现代码如下：

const int MAXN = 1005;
const int MOD = 1e9 + 7;

int C[MAXN][MAXN];

void init()
{
    for (int i = 0; i < MAXN; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
}

int main()
{
    init();
    cout << C[10][5] << endl; //输出组合数C10,5
    return 0;
}

该方法通过预先计算组合数，可以大大减少递推计算量，运行时间为$O(n^2)$。

Lucas定理

Lucas定理是一种用于解决组合数取模问题的算法。它是利用了组合数的整除性质来实现的。

Lucas定理为：$C_{m}^{n}\ \mbox{mod}\ p=C_{m\ \mbox{mod}\ p}^{n\ \mbox{mod}\ p}\cdot C_{(\lfloor\frac{m}{p}\rfloor) }^{(\lfloor\frac{n}{p}\rfloor) }$

具体实现代码如下：

const int MAXN = 1005;
const int MOD = 1e9 + 7;

int C(int n, int m, int p)
{
    if (m == 0 || n == m) return 1;
    int a[MAXN], b[MAXN];
    for (int i = 1; i <= p; i++)
        if (i % p) a[i] = a[i - 1] * i % p;
    b[p - 1] = ksm(a[p - 1], p - 2, p);
    for (int i = p - 2; i >= 1; i--)
        if ((i + 1) % p) b[i] = b[i + 1] * (i + 1) % p;
    int res = 1;
    while (n && m)
    {
        int n1 = n % p, m1 = m % p;
        if (n1 < m1) return 0;
        res *= a[n1] * b[m1] % p * b[n1 - m1] % p;
        res %= p;
        n /= p, m /= p;
    }
    return res;
}

int main()
{
    cout << C(10, 5, MOD) << endl; //输出组合数C10,5
    return 0;
}

该方法在求解组合数时，会先将n、m、p转化为p进制，然后分别计算每一位上对应组合数的值，最后通过有限域上的计算方法（同余性质）得到答案。时间复杂度为$O(p\log _p n)$，具体计算时间随p的取值有关。

特别提示

特别提示：在进行组合数计算时，如果数据范围较大，一定要取模防止溢出。