从问题到算法：组合数学在算法竞赛中的实战指南

2026-04-28 11:56:23作者：董斯意

在编程竞赛中，计数问题常常以各种形式出现，从简单的排列组合到复杂的容斥原理应用，这些问题不仅考验对数学知识的掌握，更要求将理论转化为高效的代码实现。本文将通过问题驱动的方式，带你从实际竞赛题目出发，掌握组合数学的核心方法与实战技巧，最终实现从数学原理到编程解题的跨越。

问题引入：当编程遇见组合数学

密码破解中的排列困境

你是否遇到过这样的编程竞赛题：给定一个包含重复字符的字符串，计算其所有可能的不同排列个数？例如2023 ICPC亚洲区赛第K题就考察了这一知识点。这类问题看似简单，实则涉及多重集排列的核心概念。

任务分配的组合难题

另一个经典场景是任务分配问题：将n个不同任务分配给k个团队，每个团队至少分配一个任务，有多少种不同的分配方案？这需要用到组合数学中的 Stirling 数和容斥原理，也是编程竞赛中常见的考点。

核心方法：组合数学的编程实现

排列与组合的基础计算

在编程竞赛中，排列组合的计算是基础中的基础。我们经常需要计算组合数C(n, k)，即从n个元素中选择k个元素的方案数。

组合数的递归计算

组合数有一个重要的递推关系：C(n, k) = C(n-1, k-1) + C(n-1, k)，边界条件为C(n, 0) = C(n, n) = 1。基于这个递推关系，我们可以实现一个动态规划解法。

long long comb(int n, int k) {
    if (k == 0 || k == n) return 1;
    if (k > n - k) k = n - k; // 利用组合数的对称性优化
    long long res = 1;
    for (int i = 1; i <= k; ++i) {
        res = res * (n - k + i) / i;
    }
    return res;
}

这个实现利用了组合数的对称性C(n, k) = C(n, n-k)，减少了计算量。同时，通过逐步相乘并相除的方式，避免了大数溢出的问题。

复杂度分析

上述组合数计算的时间复杂度为O(k)，空间复杂度为O(1)。对于k较小的情况，这是一个高效的实现。但当n和k都很大时（例如n=1e6, k=5e5），我们需要使用预处理阶乘和逆元的方法。

插板法：解决分配问题的利器

问题转化：从任务分配到插板模型

假设有8个相同的任务分配给3个团队，每个团队至少一个任务，有多少种分配方案？这个问题可以转化为在7个间隔中插入2个板子，即C(7, 2) = 21种方案。

算法实现

// 计算将n个相同物品分成k组，每组至少一个的方案数
long long stars_and_bars(int n, int k) {
    if (n < k) return 0; // 如果物品数少于组数，无法分配
    return comb(n-1, k-1);
}

适用边界

插板法虽然强大，但也有其适用边界：

物品必须是相同的
分组是有区别的
每组至少有一个物品（或可以转化为这种情况）

当这些条件不满足时，插板法可能会失效，需要考虑其他方法。

容斥原理：解决限制条件下的计数

问题引入：2022 ICPC网络赛第H题

题目要求计算1到n中不能被2、3、5整除的数的个数。直接计算比较困难，但使用容斥原理可以轻松解决。

算法实现

下面是容斥原理的一个实现示例，用于计算硬币组合问题：

#include <iostream>
using namespace std;
constexpr long long S = 1e5 + 5;
long long c[5], d[5], n, s;
long long f[S];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
  f[0] = 1;
  for (long long j = 1; j <= 4; j++)
    for (long long i = 1; i < S; i++)
      if (i >= c[j]) f[i] += f[i - c[j]];  // f[i]：价格为i时的硬币组成方法数
  for (long long k = 1; k <= n; k++) {
    cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
    long long ans = 0;
    for (long long i = 1; i < 16;
         i++) {  // 容斥，因为物品一共有4种，所以从1到2^4-1=15循环
      long long m = s, bit = 0;
      for (long long j = 1; j <= 4; j++) {
        if ((i >> (j - 1)) % 2 == 1) {
          m -= (d[j] + 1) * c[j];
          bit++;
        }
      }
      if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
    }
    cout << f[s] - ans << '\n';
  }
  return 0;
}

容斥原理的核心思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

实战突破：从理论到代码

卡特兰数：解决括号匹配问题

卡特兰数是组合数学中的一个重要数列，在编程竞赛中有着广泛的应用，例如求n对括号的合法匹配方式数。

卡特兰数的计算

卡特兰数的递推公式为：C0 = 1, Cn+1 = ΣCi * Cn-i (i=0 to n)

下面是一个计算卡特兰数的实现：

#include <iostream>
using namespace std;

int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // 这里用的是常见形式 4
  cout << f[n] << endl;
  return 0;
}

复杂度分析

这个实现使用了卡特兰数的closed-form公式，时间复杂度为O(n)，空间复杂度为O(n)。对于n较小的情况（如n<20），这种实现足够高效。

康托展开：排列的编码与解码

康托展开是一种将排列映射到一个唯一整数的方法，常用于生成排列、判断排列的大小关系等。

下面是康托展开的实现：

#include <cstring>
#include <iostream>
using namespace std;
constexpr int MOD = 998244353;
using ll = long long;
int n, x, d[1000005];
ll fac[1000005], ans;

int lowbit(int x) { return x & -x; }

void modify(int x, int o) {
  while (x <= n) {
    d[x] += o;
    x += lowbit(x);
  }
}

int query(int x) {
  int ret = 0;
  while (x >= 1) {
    ret += d[x];
    x -= lowbit(x);
  }
  return ret;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    d[i] = lowbit(i);                 // O(n) 建树
    fac[i] = (fac[i - 1] * i) % MOD;  // 预处理阶乘
  }
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    modify(x, -1);
    ans = (ans + ll(query(x) * fac[n - i]) % MOD) % MOD;
  }
  cout << ans + 1 << '\n';
}