08.03_组合数学

组合数学

问题描述

组合数学处理计数和排列组合问题，包括组合数计算、卡特兰数、斯特林数等。

组合数

算法思想

使用递推公式或乘法逆元
可以预处理优化计算
适用于大规模计算
时间复杂度 $\mathcal{O}(n^2)$ 或 $\mathcal{O}(n)$

代码实现

c++
java
python

class Solution {
public:
    // 递推法计算组合数
    vector<vector<long long>> combTable(int n, long long mod) {
        vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
        for (int i = 0; i <= n; i++) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; j++) {
                C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
            }
        }
        return C;
    }
    
    // Lucas定理处理大组合数
    long long lucas(long long n, long long k, long long p) {
        if (k == 0) return 1;
        return lucas(n / p, k / p, p) * comb(n % p, k % p, p) % p;
    }
    
private:
    long long comb(long long n, long long k, long long p) {
        if (k > n) return 0;
        long long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n - k + i) % p * quickPow(i, p-2, p) % p;
        }
        return res;
    }
};

class Solution {
    // 递推法计算组合数
    public long[][] combTable(int n, long mod) {
        long[][] C = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; j++) {
                C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
            }
        }
        return C;
    }
    
    // Lucas定理处理大组合数
    public long lucas(long n, long k, long p) {
        if (k == 0) return 1;
        return lucas(n / p, k / p, p) * comb(n % p, k % p, p) % p;
    }
    
    private long comb(long n, long k, long p) {
        if (k > n) return 0;
        long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n - k + i) % p * quickPow(i, p-2, p) % p;
        }
        return res;
    }
}

class Solution:
    # 递推法计算组合数
    def combTable(self, n: int, mod: int) -> List[List[int]]:
        C = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            C[i][0] = C[i][i] = 1
            for j in range(1, i):
                C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod
        return C
    
    # Lucas定理处理大组合数
    def lucas(self, n: int, k: int, p: int) -> int:
        if k == 0:
            return 1
        return self.lucas(n // p, k // p, p) * self.comb(n % p, k % p, p) % p
    
    def comb(self, n: int, k: int, p: int) -> int:
        if k > n:
            return 0
        res = 1
        for i in range(1, k + 1):
            res = res * (n - k + i) % p * pow(i, p-2, p) % p
        return res

卡特兰数

算法思想

使用递推公式 $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$
也可用组合数公式 $C_n = \binom{2n}{n} - \binom{2n}{n+1}$
适用于合法序列计数
时间复杂度 $\mathcal{O}(n)$

代码实现

c++
java
python

class Solution {
public:
    vector<long long> catalan(int n, long long mod) {
        vector<long long> cat(n + 1);
        cat[0] = 1;
        for (int i = 1; i <= n; i++) {
            cat[i] = 0;
            for (int j = 0; j < i; j++) {
                cat[i] = (cat[i] + cat[j] * cat[i-1-j]) % mod;
            }
        }
        return cat;
    }
};

class Solution {
    public long[] catalan(int n, long mod) {
        long[] cat = new long[n + 1];
        cat[0] = 1;
        for (int i = 1; i <= n; i++) {
            cat[i] = 0;
            for (int j = 0; j < i; j++) {
                cat[i] = (cat[i] + cat[j] * cat[i-1-j]) % mod;
            }
        }
        return cat;
    }
}

class Solution:
    def catalan(self, n: int, mod: int) -> List[int]:
        cat = [0] * (n + 1)
        cat[0] = 1
        for i in range(1, n + 1):
            for j in range(i):
                cat[i] = (cat[i] + cat[j] * cat[i-1-j]) % mod
        return cat

时间复杂度分析

算法时间复杂度空间复杂度

组合数递推	$\mathcal{O}(n^2)$	$\mathcal{O}(n^2)$
组合数逆元	$\mathcal{O}(n)$	$\mathcal{O}(n)$
Lucas定理	$\mathcal{O}(\log n)$	$\mathcal{O}(1)$
卡特兰数	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$

应用场景

组合计数
序列计数
路径计数
树的计数
括号匹配

注意事项

溢出的处理
取模的时机
预处理的选择
空间的优化
算法的选择

常见变形

第k个组合

cpp
java
python

class Solution {
public:
    string kthCombination(int n, int k) {
        string result;
        vector<int> nums;
        k--;  // 转为0-based
        
        // 计算组合数
        vector<vector<int>> C(n + 1, vector<int>(n + 1));
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i-1][j-1] + C[i-1][j];
            }
        }
        
        // 构造组合
        for (int i = n, left = k; i > 0; i--) {
            int j = 0;
            while (j < i && C[i-1][j] <= left) {
                left -= C[i-1][j];
                j++;
            }
            nums.push_back(j);
        }
        
        // 转换为字符串
        for (int num : nums) {
            result += ('1' + num);
        }
        return result;
    }
};

class Solution {
    public String kthCombination(int n, int k) {
        StringBuilder result = new StringBuilder();
        List<Integer> nums = new ArrayList<>();
        k--;  // 转为0-based
        
        // 计算组合数
        int[][] C = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i-1][j-1] + C[i-1][j];
            }
        }
        
        // 构造组合
        for (int i = n, left = k; i > 0; i--) {
            int j = 0;
            while (j < i && C[i-1][j] <= left) {
                left -= C[i-1][j];
                j++;
            }
            nums.add(j);
        }
        
        // 转换为字符串
        for (int num : nums) {
            result.append((char)('1' + num));
        }
        return result.toString();
    }
}

class Solution:
    def kthCombination(self, n: int, k: int) -> str:
        nums = []
        k -= 1  # 转为0-based
        
        # 计算组合数
        C = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            C[i][0] = 1
            for j in range(1, i + 1):
                C[i][j] = C[i-1][j-1] + C[i-1][j]
        
        # 构造组合
        i, left = n, k
        while i > 0:
            j = 0
            while j < i and C[i-1][j] <= left:
                left -= C[i-1][j]
                j += 1
            nums.append(j)
            i -= 1
        
        # 转换为字符串
        return ''.join(chr(ord('1') + num) for num in nums)

括号生成

cpp
java
python

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
    
private:
    void backtrack(vector<string>& result, string& current, int open, int close, int n) {
        if (current.length() == n * 2) {
            result.push_back(current);
            return;
        }
        
        if (open < n) {
            current.push_back('(');
            backtrack(result, current, open + 1, close, n);
            current.pop_back();
        }
        if (close < open) {
            current.push_back(')');
            backtrack(result, current, open, close + 1, n);
            current.pop_back();
        }
    }
};

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }
    
    private void backtrack(List<String> result, StringBuilder current, int open, int close, int n) {
        if (current.length() == n * 2) {
            result.add(current.toString());
            return;
        }
        
        if (open < n) {
            current.append('(');
            backtrack(result, current, open + 1, close, n);
            current.setLength(current.length() - 1);
        }
        if (close < open) {
            current.append(')');
            backtrack(result, current, open, close + 1, n);
            current.setLength(current.length() - 1);
        }
    }
}

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def backtrack(result: List[str], current: List[str], open: int, close: int, n: int) -> None:
            if len(current) == n * 2:
                result.append(''.join(current))
                return
            
            if open < n:
                current.append('(')
                backtrack(result, current, open + 1, close, n)
                current.pop()
            if close < open:
                current.append(')')
                backtrack(result, current, open, close + 1, n)
                current.pop()
        
        result = []
        backtrack(result, [], 0, 0, n)
        return result