L8_01 计数原理

一、加法原理

1.1 加法原理定义

若完成一件事有 n 类不同的方法，第 i 类方法有 m_i 种，则完成这件事共有 m_1 + m_2 + ... + m_n 种方法。

1.2 加法原理示例

// 计算从A地到C地的路线数
// A到B有3条路，B到C有2条路
// A到D有4条路，D到C有3条路
int routes = 3 * 2 + 4 * 3; // 18条路线

1.3 加法原理应用

// 计算集合的并集大小
// |A ∪ B| = |A| + |B| - |A ∩ B|
int unionSize(int a, int b, int intersection) {
    return a + b - intersection;
}

// 计算三个集合的并集
// |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
int unionSize3(int a, int b, int c, int ab, int ac, int bc, int abc) {
    return a + b + c - ab - ac - bc + abc;
}

二、乘法原理

2.1 乘法原理定义

若完成一件事需要 n 个步骤，第 i 个步骤有 m_i 种方法，则完成这件事共有 m_1 × m_2 × ... × m_n 种方法。

2.2 乘法原理示例

// 计算密码组合数
// 密码长度为4，每位可以是数字(0-9)或字母(a-z)
int passwordCombinations = pow(36, 4); // 36^4 = 1679616

2.3 乘法原理应用

// 计算排列数 P(n, k) = n × (n-1) × ... × (n-k+1)
long long permutation(int n, int k) {
    long long result = 1;
    for (int i = 0; i < k; i++) {
        result *= (n - i);
    }
    return result;
}

// 计算组合数 C(n, k) = n! / (k! × (n-k)!)
long long combination(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    k = min(k, n - k);
    long long result = 1;
    for (int i = 0; i < k; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

三、容斥原理

3.1 容斥原理概述

容斥原理用于计算多个集合的并集大小。

3.2 容斥原理公式

// 两个集合
// |A ∪ B| = |A| + |B| - |A ∩ B|

// 三个集合
// |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

// n个集合
// |A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - ... + (-1)ⁿ⁺¹|A₁ ∩ ... ∩ Aₙ|

3.3 容斥原理实现

// 计算[1, n]中能被a或b整除的数的个数
int countDivisible(int n, int a, int b) {
    int countA = n / a;
    int countB = n / b;
    int countAB = n / lcm(a, b);
    return countA + countB - countAB;
}

// 计算最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

// 计算最大公约数
int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

3.4 容斥原理应用：错排问题

// 计算n个元素的错排数
// D(n) = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!)
long long derangement(int n) {
    long long result = 0;
    long long factorial = 1;
    
    for (int i = 0; i <= n; i++) {
        if (i > 0) factorial *= i;
        if (i % 2 == 0) {
            result += factorial;
        } else {
            result -= factorial;
        }
    }
    return result;
}

四、鸽巢原理

4.1 鸽巢原理定义

若有 n+1 个物体放入 n 个盒子中，则至少有一个盒子包含不少于 2 个物体。

4.2 鸽巢原理扩展

若有 kn+1 个物体放入 n 个盒子中，则至少有一个盒子包含不少于 k+1 个物体。

4.3 鸽巢原理应用

// 判断是否存在重复元素
bool hasDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num)) return true;
        seen.insert(num);
    }
    return false;
}

// 证明在任何367个人中至少有两人同一天生日
bool hasSameBirthday(int n) {
    return n > 366;
}

五、排列组合综合应用

5.1 多重集合排列

// 计算多重集合的排列数
// 有n个元素，其中有k种不同元素，每种元素的个数分别为n₁, n₂, ..., nₖ
// 排列数 = n! / (n₁! × n₂! × ... × nₖ!)
long long multisetPermutation(vector<int>& counts) {
    int total = 0;
    long long result = 1;
    
    for (int c : counts) {
        total += c;
        for (int i = 2; i <= c; i++) {
            // 计算阶乘并约分
        }
    }
    
    // 计算 total!
    for (int i = 2; i <= total; i++) {
        result *= i;
    }
    
    // 除以各元素阶乘
    for (int c : counts) {
        long long fact = 1;
        for (int i = 2; i <= c; i++) {
            fact *= i;
        }
        result /= fact;
    }
    
    return result;
}

5.2 隔板法

// 计算将n个相同的球放入k个不同盒子的方法数
// C(n+k-1, k-1)
long long starsAndBars(int n, int k) {
    return combination(n + k - 1, k - 1);
}

// 计算将n个相同的球放入k个不同盒子，每个盒子至少有一个球的方法数
// C(n-1, k-1)
long long starsAndBarsAtLeastOne(int n, int k) {
    if (n < k) return 0;
    return combination(n - 1, k - 1);
}