C++基础组合计数入门指南

ljq_2029

1263人浏览 · 2025-07-12 18:46:10

ljq_2029 · 2025-07-12 18:46:10 发布

C++基础组合计数入门指南——目录

C++基础组合计数入门指南

C++基础组合计数入门指南

在算法竞赛和计算机科学中，组合计数是解决排列组合问题的基石。无论是计算排列数、组合数，还是处理多重集合的排列组合，掌握组合计数的原理和实现方法都至关重要。本文将详细介绍C++中组合计数的基础知识，包括排列与组合的定义、计算公式、性质，以及如何通过代码高效实现。

一、组合计数的核心概念

1. 加法原理与乘法原理

加法原理：完成一件事有 $n$ 类独立的方法，每类方法分别有 $m_1, m_2, \dots, m_n$ 种，则总方法数为：
$m_1 + m_2 + \dots + m_n$
即：
$\sum\limits_{i=1}^n m_i$
乘法原理：完成一件事需要分 $n$ 步，每步分别有 $m_1, m_2, \dots, m_n$ 种方法，则总方法数为：
$m_1 \times m_2 \times \dots \times m_n$
即：
$\prod\limits_{i=1}^n m_i$

示例：
由数字 $0, 1, 2, 3, 4, 5$ 组成无重复数字的五位奇数。

步骤：
1. 末位必须是奇数（ $1, 3, 5$ ），有 $C^1_3$ 种选择。
2. 首位不能为 $0$ ，且已选一个奇数，剩下 $4$ 个数字可选，有 $C^1_4$ 种选择。
3. 中间三位从剩余 $4$ 个数字中排列，有 $A^3_4$ 种方法。
总方法数：
$C^1_3 \times C^1_4 \times A^3_4 = 3 \times 4 \times 24 = 288$

二、排列与组合

1. 排列（Permutation）

从 $n$ 个不同元素中取出 $m$ 个元素并按顺序排列，记作 $A^m_n$ 或 $P (n, m)$ 。
公式：
$A^m_n = \frac{n!}{(n-m)!} = n \times (n-1) \times \dots \times (n-m+1)$
即：
$A^m_n =\prod\limits_{i=n-m+1}^n i$

2. 组合（Combination）

从 $n$ 个不同元素中取出 $m$ 个元素但不考虑顺序，记作 $C^m_n$ 。
公式：
$C^m_n = \frac{A^m_n}{m!} = \frac{n!}{m!(n-m)!}=\frac{\prod\limits_{i=n-m+1}^n i}{m!(n-m)!}$

性质：

$C^m_n = C^{n-m}_n$ （对称性）。
$C^m_n = C^{m-1}_{n-1} + C^m_{n-1}$ （递推关系）。
$\sum\limits_{i=0}^n C^i_n = 2^n$ （子集总数）。

示例：
从 $7$ 种不同的花中选出两种特殊的葵花，要求它们不在中间或两边的位置。

步骤：
1. 特殊葵花的位置有 $A^2_4$ 种选择（中间和两边除外）。
2. 剩余 $5$ 种花任意排列，有 $A^5_5$ 种方法。
总方法数：
$A^2_4 \times A^5_5 = 12 \times 120 = 1440$

三、组合数的计算方法

方法1：递推法（杨辉三角）

利用组合数的递推关系 $C^m_n = C^{m-1}_{n-1} + C^m_{n-1}$ ，预处理所有可能的组合数。
时间复杂度： $O(n\times m)$
代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cout << "Enter n and m: ";
    cin >> n >> m;
    vector<vector<int>> c(n + 1, vector<int>(m + 1, 0));
    c[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= min(i, m); j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    cout << "C(" << n << "," << m << ") = " << c[n][m] << endl;
    return 0;
}

方法2：阶乘与逆元（快速计算）

通过预处理阶乘和逆元，直接计算组合数。
公式：
$C^m_n = \frac{n!}{m!(n-m)!} = n! \times \text{inv}(m!) \times \text{inv}((n-m)!)$
其中， $\text{inv}()$ 函数用于计算矩阵的逆矩阵。如果矩阵 $A$ 是一个方阵且可逆（非奇异），那么 $\text{inv}(A)$ 将返回其逆矩阵 $A^{-1}$ ，满足 $\times A^{-1}=A^{-1} \times A = I$ ，其中 $I$ 是单位矩阵，即 $\text{inv}(A)=A^{-1}$ 。
时间复杂度： $O (n)$
代码示例：

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

// 快速幂求逆元
long long power(long long a, long long p) {
    long long res = 1;
    while (p) {
        if (p % 2) res = res * a % MOD;
        a = a * a % MOD;
        p /= 2;
    }
    return res;
}

int main() {
    int n, m;
    cout << "Enter n and m: ";
    cin >> n >> m;
    m = min(m, n - m); // 利用对称性优化
    vector<long long> fact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    long long numerator = fact[n];
    long long denominator = fact[m] * fact[n - m] % MOD;
    long long inv_denominator = power(denominator, MOD - 2);
    long long result = numerator * inv_denominator % MOD;
    cout << "C(" << n << "," << m << ") = " << result << endl;
    return 0;
}