组合数 (Combinatorics) 模板详解

组合数 (Combinatorics) 模板详解

1. 简介

组合数计算是竞赛中常见的数学问题。本模板实现了高效的组合数计算，支持阶乘、逆元和二项式系数的快速计算。模板采用预处理的方式，结合逆元优化，实现了 O(1) 的查询复杂度。

主要特点：

  • 支持动态扩容的预处理
  • O(n) 的预处理时间复杂度
  • O(1) 的查询时间复杂度
  • 支持阶乘、逆元和组合数计算

2. 实现原理

2.1 基本概念

  1. 阶乘：

    • n! = n × (n-1) × … × 2 × 1
    • 用于计算排列组合数

  2. 逆元：

    • 在模运算下的乘法逆元
    • 用于处理除法运算

  3. 组合数：

    • C(n,m) = n! / (m! × (n-m)!)
    • 表示从n个物品中选m个的方案数

2.2 核心策略

  1. 预处理：

    • 预处理阶乘和阶乘逆元
    • 动态扩容避免内存浪费

  2. 逆元优化：

    • 使用费马小定理计算逆元
    • 利用逆元处理除法运算

3. 模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct Comb {
    int n;
    std::vector<Z> _fac;    // 阶乘
    std::vector<Z> _invfac; // 阶乘逆元
    std::vector<Z> _inv;    // 逆元
    
    // 构造函数
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    // 初始化函数
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        // 计算阶乘
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        
        // 计算阶乘逆元
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    // 获取阶乘
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    
    // 获取阶乘逆元
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    
    // 获取逆元
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    
    // 计算组合数
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

4. 函数说明

4.1 构造和初始化

1
2
3
Comb()
Comb(int n)
void init(int m)
  • 支持默认构造和指定大小构造
  • 动态扩容的初始化函数

4.2 核心操作

1
2
3
4
Z fac(int m)
Z invfac(int m)
Z inv(int m)
Z binom(int n, int m)
  • fac: 计算阶乘
  • invfac: 计算阶乘逆元
  • inv: 计算逆元
  • binom: 计算组合数

5. 时间复杂度分析

  • 初始化：O(n)

    • 阶乘预处理：O(n)
    • 逆元预处理：O(n)

  • 查询操作：O(1)

    • 所有查询操作均为常数时间
    • 动态扩容时需要 O(n) 的预处理

  • 空间复杂度：O(n)

    • 存储阶乘、逆元等数组

6. 应用场景

  1. 排列组合计算
  2. 概率统计问题
  3. 动态规划优化
  4. 组合数学问题
  5. 生成函数计算

7. 使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 初始化组合数计算器
Comb comb(100);  // 预处理到100

// 计算组合数 C(5,2)
Z result = comb.binom(5, 2);

// 获取阶乘 5!
Z factorial = comb.fac(5);

// 获取逆元
Z inverse = comb.inv(3);

// 动态扩容示例
Z large_comb = comb.binom(200, 100);  // 自动扩容

8. 注意事项

  1. 所有计算都在模意义下进行
  2. 需要保证模数为质数（费马小定理）
  3. 动态扩容会导致一次 O(n) 的预处理
  4. 组合数计算要注意参数的合法性

9. 总结

本模板通过预处理和逆元优化，实现了高效的组合数计算。它不仅支持基本的组合数计算，还提供了阶乘和逆元等功能，是解决组合数学问题的有力工具。