组合数学：从入门到入坟

paulpao · 2026-08-07 17:20:03 · 算法·理论

前言

本文难度跨度较大，从绿题到黑题不等，既有对基本定义的介绍，也有对较综合习题的讲解，如果你对基础知识足够了解，可以直接跳到最后一章。

一. 排列与组合

1. 定义

从一个 n 元集合中选出 m 个数，按顺序排成一个有序序列，这样的方案数称为排列，记作 P_{n}^{m}。

序列的顺序性是关键，不同顺序视为不同排列。如 1,2,3 与 1,3,2 是不同排列。

排列的计算很简单，第一项有 n 种选法，第二项有 n-1 种，第三项有 n-2 种，依此类推，第 m 项有 n-m+1 种选法。

因此 P_{n}^{m}=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}。

从 n 个元素中选出 m 个元素构成一个子集，子集不区分顺序，这类方案数称为组合数，记作 C_{n}^{m} 或 \binom{n}{m}，由于后者看起来比较高级，本文采用后者。

同一组元素的不同排列在组合中被视为同一种情况。如 1,2,3 与 1,3,2 是同种组合。

组合数可通过排列数去除重复计数得到：由于 m 个元素有 m! 种排列，在组合中均视为相同。

因此，\binom{n}{m}=\frac{P_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}。

2. 预处理

方法 1：帕斯卡恒等式（O(n^2)-O(1)）。

首先有 \binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}。

:::info[证明]
分类讨论，使用组合意义证明。

• 第 n 个元素如果被选择了，那么有 \binom{n-1}{m-1} 种情况，因为要在前 n-1 个元素里选 m-1 个。
• 第 n 个元素如果没被选择，那么有 \binom{n-1}{m} 种情况，因为要在前 n-1 个元素里选 m 个。

其次我们知道 \binom{n}{0}=1 \ (n \in \mathbb N)，因为从 n 元集中选 0 个只有空集一种选法。

那么我们就可以利用这两个式子做 DP 了，时间复杂度预处理 O(n^2)，查询 O(1)。

这种方法好实现，但效率低下，下面介绍一种更高效的方法。

方法 2：逆元预处理（O(n)-O(1)）。

首先，前文已经提到了组合数公式，即 \binom{n}{m}=\frac{n!}{m!(n-m)!}。

如果范围较小，我们可以直接用这个公式计算出结果，都不用预处理。

但是这个公式增长起来是很快的，分子随便爆 long long。OI 不会搞狗屎高精度，所以题目里一般会有素数模数 P，让你对这个数取模，我们引入有理数取模方法。

我们认为 \frac{p}{q}\equiv a\pmod P 当且仅当 p\times q^{-1}\equiv a\pmod P，其中 q^{-1}\times q\equiv1\pmod P 且 q^{-1}\le P，一般 P 是素数，所以大部分情况下 q^{-1} 存在且唯一，称为 P 的逆元，在模意义下，除以一个数等于乘其逆元。

那么我们可以预处理出所有阶乘和阶乘逆元，就可以 O(1) 求组合数了。阶乘逆元直接递推即可，下面讨论怎么预处理阶乘逆元。

由费马小定理，1 \equiv a^{P-1}\pmod{P}\Rightarrow a^{-1} \equiv a^{P-2}\pmod{P}。我们可以使用快速幂 O(\log P) 求 n! 逆元 (n!)^{-1}。

我们利用递推关系反向求解：((n-1)!)^{-1} \equiv (n!)^{-1} \times n\pmod P，两边同乘 n! 易知该式成立。这样我们就可以在 O(n) 复杂度内预处理出所有阶乘逆元。

注意要处理 0!=1 以及 (0!)^{-1}=1。

参考代码：

#include<iostream>  
#include<cstdio>  
#include<queue>  
#include<vector>  
#define int long long  
using namespace std;  
const int N=3e6+5;  
const int mod=1e9+7;  
int ksm(int a,int b){  
    int ans=1;  
    while(b){  
        if(b%2){  
            b--;  
            ans*=a;  
            ans%=mod;  
        }  
        b/=2;  
        a*=a;  
        a%=mod;  
    }  
    return ans;  
}  
int jc[N],jcn[N];  
void ini(){  
    jc[0]=1;  
    jcn[0]=1;  
    for(int i=1;i<=N-2;i++){  
        jc[i]=jc[i-1]*i;  
        jc[i]%=mod;  
        jcn[i]=ksm(jc[i],mod-2);  
    }  
}  
int C(int a,int b){  
    if(b>a) return 0;  
    return jc[a]*jcn[b]%mod*jcn[a-b]%mod;  
}  
int A(int a,int b){// 这种方法同样适用于求排列数  
    if(b>a) return 0;  
    return jc[a]*jcn[a-b]%mod;  
}  

3. 例题

P3223 排队

这题原题要高精度，现代的 OI 基本不会考高精，甚至作者校内 OJ 直接加了个模数，因此参考代码对 10^9+7 取模了。

:::info[Hint1]
如果只有男生女生，没有老师，怎么搞？
:::
:::success[Hint1答案]
组合数学常用技巧：插空法。

显然男生直接排成一排，共 n! 种方法。下面我们讨论插空的方法，我们把老师也带上，分两类讨论。

• 老师插在不同的空，先把老师放好，共 A_{n+1}^{2}，然后老师就和男生没区别了，相当于有 n+2 个男生，女生有 A_{n+3}^{m} 种排列方法。这类情况共 A_{n+3}^{m}\times A_{n+1}^{2} 种。
• 老师插在同一个空，中间一定要有一个女生，这个 oxo 单元组共 2m 种可能性，可以放在 n+1 个空里，然后这个单元组等价于一个男生，剩下的女生共 A_{n+2}^{m-1} 种排法。

:::success[code]

#include<iostream>  
#include<cstdio>  
#include<queue>  
#include<vector>  
#define int long long  
using namespace std;  
const int N=3e6+5;  
const int mod=1e9+7;  
int ksm(int a,int b){  
    int ans=1;  
    while(b){  
        if(b%2){  
            b--;  
            ans*=a;  
            ans%=mod;  
        }  
        b/=2;  
        a*=a;  
        a%=mod;  
    }  
    return ans;  
}  
int jc[N],jcn[N];  
void ini(){  
    jc[0]=1;  
    jcn[0]=1;  
    for(int i=1;i<=N-2;i++){  
        jc[i]=jc[i-1]*i;  
        jc[i]%=mod;  
        jcn[i]=ksm(jc[i],mod-2);  
    }  
}  
int C(int a,int b){  
    if(b>a) return 0;  
    return jc[a]*jcn[b]%mod*jcn[a-b]%mod;  
}  
int A(int a,int b){  
    if(b>a) return 0;  
    return jc[a]*jcn[a-b]%mod;  
}  
signed main(){  
    int n,m;   
    cin>>n>>m;  
    ini();  
    cout<<jc[n]*(C(n+1,1)*m%mod*2%mod*A(n+2,m-1)%mod+A(n+1,2)*A(n+3,m)%mod)%mod;  
    return 0;  
}   

:::

CF1420D Rescue Nibel!

:::info[形式化题意]
给定 n 个区间 [l_i,r_i]，你需要找出 k 个区间，使其交集不为空。
:::
:::info[Hint1]
两个区间 [l_i,r_i] 与 [l_j,r_j] 交集不为空等价于 l_j\le r_i 或 l_i\le r_j，可以根据 l 排序消掉一维。
:::
:::info[Hint2]
固定选择的左端点最大的区间，找出所有与其有交集的区间。
:::
:::success[Solution]
先把区间根据左端点排序，现在两个区间有交等价于 r_j\ge l_i，我们考虑固定每个区间作为左端点最靠右的选择区间时的方案数，那就是在和他有交的区间中选 k-1 个，即方案数为 \binom{cnt}{k-1}，cnt 为与其有交区间个数。

• 当 k=j 时，l_{i,j,k}\gets\min(l_{i,j,k},l_{i+1,j,k})

• 当 k=i 时，l_{i,j,k}\gets\min(l_{i,j,k},l_{i,j-1,k})

CF1770F Koxia and Sequence

::::success[Step 1：对称性] 下文中的 a 指的是一个好数组。

由题意得，答案为：

交换异或顺序，得答案为：

也就是说，我们可以分别考虑每个位置对答案的贡献。

由于每个位置的数有对称性，因此对于每个 i，\bigoplus_{a}a_i 都相等，设为 v。

下文中用集合形式表示数，即 i\in a_1 表示 a_1 第 i 位为 1。

定义 H(S) 表示和为 x 且按位或为 S 的好数组方案数，G(S) 表示和为 x 且按位或结果 \subseteq S 的方案数，那么 G(S) 很好用 H(S) 表示。

然后我们可以子集反演，得：

这个公式感性理解一下吧，我也不会证。

由于我们只关心 H(S) 奇偶性，那么两边 \bmod 2 由于 -1\equiv1\pmod 2，所以神奇的是，-1 全消掉了！

而且模 2 意义下，求和就是异或，那么可知：

我们再定义 H_i(S) 是 i\in a_1 且和为 x 且按位或为 S 的好数组方案数，G_i(S) 是 i\in a_1 且和为 x 且按位或 \subseteq S 的好数组方案数。那么有：

如果 i\notin T 则显然 G_i(T)=0。a_1 有限制，其他没限制，我们把 T\subseteq y 和 i\in a_1 转化为 a_1-2^i\subseteq T-2^i。

那么：

::::
::::success[Step 4：逆用 Lucas 定理]
首先，由 Lucas 定理 \binom{n}{m}\equiv[m\subseteq n]\pmod 2。

那么

::::
::::success[Step 5：范德蒙德卷积]
由范德蒙德卷积，G_i(T)\equiv\binom{nT-2^i}{x-2^i}\equiv[i\in T][(x-2^i)\subseteq(nT-2^i)]，然后我们枚举每一位再枚举 T 分别计算。

CF1603E A Perfect Problem
:::success[引理 1]
一个序列是否完美与其顺序无关，因此我们先将原序列排序后处理。
:::
:::success[引理 2]
一个排好序的序列完美当且仅当其所有子区间是好的。
::::info[证明]
必要性显然。

::::info[证明]
由于 a_1a_i\ge\sum_{j=1}^{i}a_j\ge ia_1。

::::info[证明]
由引理 4，b_i=a_i-a_1\ge i-a_1。

从而 \sum_{i=1}^{n}b_i\ge\sum_{i=a_1+1}^{n}(i-a_1)=\frac{(n-a_1)(n-a_1+1)}{2}。

但是又由引理 5 可得，a_1\ge\sum_{i=1}^{n}b_i。

从而可得 a_1\ge\frac{(n-a_1)(n-a_1+1)}{2}。

::::success[Solution]
枚举最小值 a_1，定义 dp_{i,j} 表示当前选了 i 个数，前缀和为 j 的方案数，从小到大依次枚举每个数以及其选的个数。DP 即可。 ::::