企业官网建设流程全解析

1. 一个学弟的困惑：排序和贪心都刷了，看到“方案数”还是会慌

前阵子一个学弟找我诉苦，说他刷了大半年算法题，链表、二叉树、排序、双指针这些常规题基本都能啃下来，可只要题目里出现“有多少种方案”“一共有多少种排列”“求方案总数，并对 1e9+7 取模”这种表述，他心里就开始发怵。他说了一句让我印象特别深的话：“我知道要动态规划，但状态定义完了之后，转移方程怎么写完全靠蒙。”

这其实就是组合数学没入门的典型症状。组合数学在大学课程里往往被讲成了一门背公式的课：排列数、组合数、二项式定理、容斥原理、鸽巢原理……每一块单独拿出来都认识，但一面对算法题，这些知识就好像在脑子里各自为战，根本调用不起来。为什么？因为它真正的价值从来不在公式本身，而在公式背后那套离散结构的拆解方式。

这篇内容我想换个视角来聊组合数学：不按教科书章节讲，而是按算法实战里真正需要的能力来拆。你可以把它当成一份写给算法学习者的组合数学“转译手册”，里面会交替出现数学推导、代码实现和踩坑经验。写完你再看那些计数类问题，至少能有几条清晰的思路线可以走。

先说清楚组合数学在算法世界里到底管什么。它研究的是离散对象的计数、排列、存在性和构造问题。对应到算法题里就是几类很具体的问题：第一类是数方案，像“从 n 个物品里选 k 个”“n 对括号能组成多少合法序列”；第二类是判断是否存在，像抽屉原理类题目，题目不会让你构造，而是让你证明某个结构必然出现；第三类是给算法分析提供工具，比如排序算法为什么最快也是 O(n log n)，背后需要用到组合计数的下界估算。这三类能力恰好是算法学习从“会写代码”走向“会设计算法”的关键台阶。

接下来的内容，会围绕一条主线走：先讲清计数的最底层逻辑，再做组合数计算的工程化选型，然后过渡到递推和动态规划、生成函数，再到几类高频经典序列，最后聊聊存在性思维和复杂度下界。这个顺序基本对应了一个人从“能数数”到“会建模”的完整进阶路径。

2. 数数的两种底层姿势：加法原理和乘法原理没你想的那么简单

组合数学的起点往往朴素到让人忽略，不过是小学奥数就接触过的加法原理和乘法原理。但恰恰是这两条原理，决定了所有复杂计数题的拆解方向。很多人在考场上想不出转移方程，不是因为不会动态规划，而是因为在“分步”和“分类”这个最源头的选择上就已经歪了。

加法原理说的是：一件事如果能够分成 n 类互斥的做法，那总的方案数就是各类方案数相加。它对应到程序里就是一个 for 循环做累加，对应到动态规划里就是状态转移方程里多个来源项的和。举例来说，从甲地到乙地可以坐公交、地铁、打车，公交有 3 趟、地铁有 2 条线、打车有 4 种叫车方式，那么总方案数就是 3+2+4=9。这里的关键约束是“互斥”，也就是任何两种方式不能同时算作一条完整路径。

乘法原理则是分步。一件事需要依次完成 n 个步骤，第 i 步有 a_i 种选择，那么总方案数是各个步骤选择数的乘积。就像设定一个三位密码锁，每一位有 10 种数字可选，总密码数就是 10×10×10=1000。到算法题里，乘法原理几乎渗透在所有树形结构计数中：根节点选了某一种状态，左右子树各自独立计数，方案数就是子树计数的乘积，从二叉搜索树计数到区间 DP，底层全是这个逻辑。

但真正考验功力的地方在于，很多问题并不是一眼能看出该用加法还是乘法，而是要你先做一次逻辑拆解。拆错了，公式套得再熟也是错的。我实际做题时常用的判断标准是：问自己“完成整件事，是所有方法里我只需选其中一种，还是要把所有步骤都做完”。选择其中一个方案就有加法关系；必须把多个环节依次凑齐，就有乘法关系。

有时候一道题里会嵌套两种原理。考虑最经典的“从 n 个不同物品中取 k 个排成一列”的排列数问题：第一个位置有 n 种选择，第二个位置有 n-1 种选择，一直乘到第 k 个位置有 n-k+1 种选择。这是一个典型的乘法原理过程。但如果你想问的是“不排序地选出 k 个物品”，那得先按排列数乘出来，再除以 k 个物品内部的全排列数 k!，因为每一种“无序选择”都被重复计算了 k! 次。这里除法去重本质上就是在处理“某种分类被重复计数”的问题。

正是这个“先乘后除”的思路，让我在算法题里少走了很多弯路。因为程序处理重复计数远不如数学式子灵巧，所以很多组合计数题的正确建模方式，是先构造一个有顺序的计数过程，再通过对称性消掉顺序带来的重复。只要你意识到题目中的对象是有顺序区分的，计数就立刻简单了。

3. 容斥原理：正面数不清楚的时候，先把“脏东西”减掉再加回来

组合计数里最反直觉、却又最高频的技巧，是容斥原理。它解决的是“多个条件同时成立”的计数问题。直接数满足 A 或 B 或 C 的对象个数很麻烦，但数“完全不满足任何条件”的对象数往往很简单。容斥原理的精髓就是先把全部对象数一遍，再减掉不想要的，把减多的加回来，循环往复。

具体公式是：|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|。奇数个集合相交就加，偶数个集合相交就减。看着像死记硬背，其实背后逻辑很朴素：把所有对象当成全集，第一次把属于 A 的挑出来，但 B 和 C 的元素也被算了；于是减掉两两交集，但三个集合共同的部分被减没了；所以要再加回来。这跟你在代码里做去重时，用位掩码标记状态再逐个检查是一模一样的逻辑。

举一个能立刻上手的例子：1 到 60 的整数中，既不是 2 的倍数、也不是 3 的倍数、还不是 5 的倍数的数有多少个？正面枚举当然可以做，但手算很累。用容斥：总数 60，是 2 的倍数的有 30 个，是 3 的倍数的有 20 个，是 5 的倍数的有 12 个；同时被 2 和 3 整除即 6 的倍数有 10 个，同时被 2 和 5 整除即 10 的倍数有 6 个，同时被 3 和 5 整除即 15 的倍数有 4 个；同时被三个数整除即 30 的倍数有 2 个。那么结果就是 60 - 30 - 20 - 12 + 10 + 6 + 4 - 2 = 16。验算一下心里就踏实了，这个 16 跟暴力枚举完全一致。

在算法题里，容斥原理最常见的用法是把“至少满足一个条件”转换成“一个都不满足”，再枚举所有条件子集。如果有 m 个限制条件，就枚举 2^m 个子集，根据子集大小决定加还是减。这样一个乍看起来需要多重循环嵌套的问题，复杂度变成 O(2^m)，在 m 不大的时候非常优雅。

注意，容斥原理用于算法题时需要配合最小公倍数计算重合部分。比如“同时是 a 和 b 的倍数”的个数是 n / lcm(a, b)，而不是 n / (a×b)。这个坑我在初学的时候踩过不止一次，两个互质的时候恰好相等会被掩盖掉，一旦遇到不互质的数，比如 4 和 6，直接相乘就会多算或漏算。

在实际比赛里，容斥还经常跟二分答案挂钩。比如问“第 k 个不被 a_1, a_2, ..., a_m 中任何一个数整除的正整数是多少”，你先二分这个数 x，然后用容斥在 O(2^m) 内算出 1 到 x 中有多少个符合要求的数，再往右压缩。这类题一出现，基本上就是在考察你容斥这个基本功。所以别小看这个公式，它并不是一个只存在于考卷角落的冷门知识。

4. 组合数的正确计算方式：n=20 和 n=1e6 用的完全不是同一套方法

几乎所有组合数学问题最终都会落到求组合数 C(n, k) 上。但“求”这件事，在不同数据范围下解法完全不同。很多初学者拿到公式 C(n, k) = n! / (k!(n-k)!)，就直接写一个阶乘函数去算，结果 n 到 30 就溢出，到 100 就已经慢得看不下去了。选错算法，不是优化问题，而是方向问题。

先给一张选型对照表，后面再逐个解释：

第一种，杨辉三角递推，用的是 C(n, k) = C(n-1, k-1) + C(n-1, k)。这个递推式的含义本身就是组合数学的重要结论：第 n 个物品要么被选中，那就是从剩下 n-1 个里再取 k-1 个；要么没被选中，那就是从剩下 n-1 个里取 k 个。两类互斥，方案数相加。这个公式在所有 n 比较小、模数不确定、需要频繁查询的场景下极其好用。你把 n×k 的二维表全部填一遍，之后任意查询都是 O(1) 的事。很多动态规划题里，这个二维表本身还承担“辅助状态”的角色，算着算着就需要查一个组合数。

第二种，阶乘逆元法，是比赛里最常用的。思路是先预处理出 0! 到 n! 对模数取模后的值，再用费马小定理求出 n! 的逆元，组合数就能用三个阶乘值拼出来。原理不复杂：模数是素数 p 时，任意不是 p 的倍数的数都有逆元。代码写出来大概是这样：

MOD = 10**9 + 7 def init_fact(n): fact = [1] * (n + 1) inv_fact = [1] * (n + 1) for i in range(1, n + 1): fact[i] = fact[i - 1] * i % MOD inv_fact[n] = pow(fact[n], MOD - 2, MOD) for i in range(n, 0, -1): inv_fact[i - 1] = inv_fact[i] * i % MOD return fact, inv_fact def comb(n, k, fact, inv_fact): if k < 0 or k > n: return 0 return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

第三种情况，n 大到 10^18，模数却是一个比较小的素数，比如 1e5+7，那阶乘预处理到 n 根本不现实。这时要用 Lucas 定理：把 n 和 k 都写成 p 进制，分别对每一位求组合数，再乘起来。公式写出来是 C(n, k) ≡ C(n mod p, k mod p) × C(n // p, k // p) (mod p)。Lucas 定理成立的关键前提是模数为素数，条件不满足时就得另想办法，比如扩展 Lucas，但那是另一个更深的坑。

还有一类场景不需要取模，要求精确输出完整数字。这在有些打卡题里会出现。直接用高精度阶乘再除会非常慢，更聪明的做法是把分子分母分别做质因数分解，约分完再乘。换句话说，先算出 n! 里每个质因子的指数，再减去 k! 和 (n-k)! 里的指数，剩下的指数直接乘起来，不会产生任何除法，天然规避了“大数除以大数”的精度问题。

说到除法，这里必须预警一个比赛里的高频失分点：在模运算体系下，“除以一个数”是乘上它的逆元，不是真的去做小数除法。不少初学者把 C(n, k) 直接写成 fact[n] / (fact[k] * fact[n-k]) % MOD，这种写法的结果往往错得悄无声息。因为普通除法在大整数环境下根本不能保证模意义下的正确性。养成习惯：所有取模后的乘除法，都是乘法运算，遇到除就找逆元。

5. 递推关系：组合数学里的状态转移，比动态规划的名字出现得更早

动态规划里总说状态转移方程，实际上组合数学里研究递推关系比算法竞赛早了不知道多少年。递推关系就是“大问题的结果由若干小问题的结果组合而成”，这和 DP 完全同构。区别只在于：DP 的转移需要你从题目里现想，而很多经典组合对象的递推关系已经被前人研究透了，你可以直接拿走用。

最典型的例子是错排问题：n 个元素都放错位置的排列数 D(n)。大名鼎鼎的递推式是 D(n) = (n-1)(D(n-1) + D(n-2))，初值 D(1)=0，D(2)=1。这个公式的推导非常漂亮：考虑第 n 个元素，它不能放在位置 n，所以只能放到 1 到 n-1 中的某个位置 i，一共有 n-1 种放法。接下来分类讨论：如果原来在位置 i 的元素恰好被放到了位置 n，那么剩下 n-2 个元素要完成错排，方案数是 D(n-2)；如果原来在位置 i 的元素没有放到位置 n，那它要么去其他位置，总之剩下 n-1 个元素还要完成错排，方案数是 D(n-1)。两类互斥，乘上第 n 个元素选择位置 i 的 n-1 种方式，就得到递推式。

这个递推式翻译成代码，就是动态规划数组的转移：

def derangement(n): if n == 1: return 0 if n == 2: return 1 dp = [0] * (n + 1) dp[1] = 0 dp[2] = 1 for i in range(3, n + 1): dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD return dp[n]

为什么我说这是理解 DP 的绝佳材料？因为一般的 DP 题，状态转移方程是你要自己从题目语义里提炼的，错了也无从对照。但错排的递推式有严格的组合解释，你可以把“递推式推导”当成一种 DP 建模的手感训练。多推几回，再看那些需要自己定义状态的题，思路会清晰很多。

另一类值得掌握的是线性常系数递推如何求通项，以及高阶递推如何用矩阵快速幂加速。我们熟知的斐波那契数列 F(n) = F(n-1) + F(n-2)，朴素递推是 O(n)，但 n 到 10^18 时，只能靠矩阵快速幂。把递推写成矩阵形式：

| F(n+1) | | 1 1 | | F(n) | | F(n) | = | 1 0 | × | F(n-1) |

矩阵的 n 次方可以用快速幂在 O(log n) 时间里算完。这个手法本质是把线性递推转化为矩阵连乘，在很多“看似组合数学但实际求第 n 项”的题目里都通用。关键是识别出递推式是否线性、系数是否常数，以及快速幂的矩阵乘法是否有结合律。

有一点容易被忽略：递推关系在组合数学里不只是用来“算数”，更是一种存在性证明工具。很多情况下你未必能直接写出闭式公式，但只要递推式存在，你就能在有限步内算出任意项。这种“能算就算，不追求一棍子到底”的思路，恰好也是算法工程里的务实态度。

6. 生成函数与卡特兰数：多项式展开就把计数问题吞掉了

聊完递推，必然要引出生成函数。生成函数这东西刚接触时常让人摸不着头脑：你告诉我一个无穷级数，怎么就能计数了？我的理解更朴素：生成函数是一个把“选择过程”翻译成多项式乘法的工具。每一项前面的系数，就是对应取值下的方案数。

举个例子，如果你的问题是“有一个苹果、一个橘子和一个香蕉，每个水果最多选一个，问选 1 个水果有几种方案，选 2 个有几种方案”，那么每个水果对应一个因子“1 + x”。展开 (1+x)(1+x)(1+x) = 1 + 3x + 3x² + x³，x 的指数是选了几个水果，系数就是对应方案数。x² 的系数是 3，因为你确实有苹果+橘子、苹果+香蕉、橘子+香蕉三种选法。

把思路推广：如果每种水果可以选任意多个，每个因子就是 1 + x + x² + ... = 1/(1-x)。如果物品带有重量、价值等附加属性，把 x 的指数换成属性总和，便可以用来统计“总重量为某个给定值的选择方案有多少”。这在背包问题里是一个极其直观的视角：做背包的 DP 循环，本质上就是在做这种多项式乘法，只是通常用数组存储系数而已。

生成函数最大的杀招在于，它能把你从无穷无尽的分类讨论里解放出来。比如卡特兰数的生成函数推导：记 C_n 表示 n 对括号能组成的合法序列数量，C_0=1。观察任意一个合法括号序列，第一个字符必然是左括号，与它匹配的右括号会把整个序列切成两部分——外层括号内的子问题和对剩余部分的子问题。这个结构直接给出递推关系 C_n = sum_{i=0}^{n-1} C_i C_{n-i}，也就是卡特兰数的经典定义之一。

卡特兰数在算法题里的出现频率高得离谱，它对应的场景包括：n 个节点的不同形态二叉树数量、n 个元素通过栈的不同出栈序列数量、n 对括号的合法排列数、n+1 个矩阵连乘的完全括号化方案数、凸 n+2 边形的三角剖分数量。表面上看这些题目一点不像，但背后结构完全同构。做题时如果你发现递推式长得像卷积 C_n = sum C_i C_{n-i}，基本可以判断是卡特兰数。

# 卡特兰数前 n 项，模质数 catalan = [0] * (n + 1) catalan[0] = 1 for i in range(1, n + 1): catalan[i] = catalan[i - 1] * (4 * i - 2) % MOD * pow(i + 1, MOD - 2, MOD) % MOD

这里用的递推式是 C_n = C_{n-1} × (4n-2) / (n+1)，在模素数条件下用逆元完成除法。它的好处是能把 O(n²) 的卷积递推优化到 O(n)，在 n 到百万级别时依然能跑。对于卡特兰数，常用闭式公式还有 C_n = C(2n, n) / (n+1)，也可以直接用组合数方法来算。

除了卡特兰数，斯特林数也值得认识一下。第二类斯特林数 S(n, k) 表示把 n 个有区别的球放入 k 个无区别的非空盒子的方案数。递推式 S(n, k) = k×S(n-1, k) + S(n-1, k-1) 的推导思路是看最后一个球：它要么单独放进一个新的盒子，对应前半部分从 n-1 个球装 k-1 个盒子；要么放进已有的 k 个盒子的任意一个，对应 k×S(n-1, k)。两类情况互斥，直接相加。

第一类斯特林数则处理的是将 n 个元素分成 k 个圆排列的方案数，递推式是 s(n, k) = (n-1)×s(n-1, k) + s(n-1, k-1)。这两类数列的关系、以及它们和贝尔数、阶乘的联系，可以展开讲很多，但实战中用的更可能是识别题面：凡是有“将集合划分成 k 个子集且每个子集非空”的计数，立刻想到第二类斯特林数；凡是有“循环移位视为同一种排列”的描述，立刻想到第一类斯特林数。这个识别动作本身，就是刷题经验积累出来的“直感”。

7. 鸽巢原理与算法下界：有些结论不靠算，靠“必然存在”

组合数学还有一条跟计数不太一样的分支，研究的是存在性问题。最朴素也最锋利的工具就是鸽巢原理，也叫抽屉原理：把 n+1 个物体放进 n 个抽屉，无论如何放，至少有一个抽屉里放了至少两个物体。听起来像废话，但它在算法证明和竞赛题里威力极大，因为很多“是否存在”的问题，最终都能构造出一组合适的抽屉。

一个经典的竞赛题是这样的：从 1 到 2n 中任意选出 n+1 个正整数，证明其中一定存在两个数，一个能被另一个整除。证明手法很有代表性：把每个整数都写成 2^k × m 的形式，其中 m 是奇数。1 到 2n 里面最多只有 n 个不同的奇数，现在你选了 n+1 个数，按各自的奇数部分 m 分类，必然有两个数落到同一个奇数 m 上。于是较小的那个乘以 2 的若干次方就能得到较大的那个，整除关系成立。这个思路的关键在于“把奇数部分相同的数放进同一个抽屉”，一共只有 n 个抽屉，而你选了 n+1 个元素。

再看一个更贴近编程的版本：任意 n 个整数中，一定存在一个连续子段，其和能被 n 整除。构造方法是用前缀和 S_0, S_1, ..., S_n 一共 n+1 个值，把它们全部对 n 取余。余数只有 0 到 n-1 这 n 种情况，根据鸽巢原理，必然有两个前缀和同余，这两个前缀和对应的区间就是答案。放到算法里，这意味着你不需要暴力枚举所有子区间，而是用这个原理指导你做前缀和模运算，再配合哈希表找重复余数。题感强的人看到“连续子段和能被整除”这几个字，立刻就应该想到这条路径。

鸽巢原理还能延伸出算法分析里最漂亮的一个结论——比较排序的下界。为什么任意基于比较的排序算法在最坏情况下至少需要 O(n log n) 次比较？你不能用快速排序的平均表现或归并排序的稳定性来回答，因为问的是“任意比较排序都不可能更快”。可以把整个排序过程看成决策树：每次比较产生两个分支，最终叶子节点必须覆盖所有 n! 种可能的排列。树高如果是 h，最多只有 2^h 个叶子，所以必须有 2^h ≥ n!，推出 h ≥ log₂(n!) ≈ n log₂ n。n! 在这里就是组合数学意义上的排列计数。

这种下界思维对算法设计的启发是：有些优化不是因为你代码写得不够好，而是理论已经封死了天花板。知道这个以后，你就不会再浪费时间试图设计一个“O(n log n) 以下的通用比较排序”。这个意识，是只有学过组合数学的人才会有的一种“算法审美”。

不过也要提醒一句，鸽巢原理类题目难点往往在抽屉构造上，而不在理解原理本身。构造的常见套路有三种：按奇偶分类、按模 n 的余数分类、按二进制拆位分类。拿到题的瞬间先别急着套公式，多想想题目给的这个数据范围暗示了什么分组方式。这跟前面讲的组合计数是一个道理，工具本身简单，难的是你能不能识别出那个关键的分组维度。

8. 给入门者的实践建议：组合数学到底怎么学才算“学进脑子里了”

最后聊点实际操作。很多人学组合数学的方式是抱着教材啃，从集合论开始，一章一章往下看，看到生成函数基本就放弃了。我不建议这么学。要我说，组合数学的实践性很强，它必须在题目里被反复验证，才真正长在你身上。

我的建议是第一轮先掌握四件事：排列组合的公式及组合数计算的各种边界条件、加法乘法原理和容斥原理、经典递推关系（错排、卡特兰数至少覆盖）、鸽巢原理的构造思路。这四样东西覆盖了竞赛和面试里大约八成直接用到组合数学的场景。把上面的代码自己敲一遍，再去找对应的题刷上十道左右，基本能形成条件反射。

第二轮再深入生成函数和斯特林数。这时候最好配合自己的实际需求：如果目标是面试大厂，掌握卡特兰数的应用场景和组合数取模已经足够；如果目标是算法竞赛，再往生成函数、Polya 计数定理的方向走也来得及。别指望一口气吃成胖子，组合数学的内容每年都能看到新的应用方向，它的知识树是越遍历越大的。

刷题时我有一个很土但很有效的习惯：看到一道和计数有关的题，先不着急写代码，而是先写暴力枚举程序，把 n 较小的情况的前几项数列打出来。比如 n=1,2,3,4,5 的结果分别是 1, 2, 5, 14, 42，那基本就要往卡特兰数上去想；如果是 0, 1, 2, 9, 44，就查一下错排或贝尔数。这个“先算小数据、对数列、再套模型”的工作流，能避免你对着题目凭空猜测数学结构，能够显著提升识别率。

有条件的话可以使用 OEIS（在线整数数列百科）这个网站来辅助识别数列。把自己暴力枚举出的前几项输入进去，如果查到了很多已有序列，那说明你手头的计数对象很可能是经典结构，顺着已知递推式逆推回题目语义，往往事半功倍。但这只能作为辅助工具，不能替代自己推导，否则换一道题稍微变化一下，你还是会认不出来。

还要强调一件反直觉的事情：组合数学刷题的正确姿势不是背公式，而是反复读题面里的“对象是否有区别”“盒子是否有区别”“顺序是否重要”“是否允许为空”。这四个问题只要有一个理解错，结果就是天壤之别。比如同样是“放球问题”，n 个有区别的球放进 k 个有区别的盒子且允许空盒，答案是 k^n；而球有区别、盒子无区别、盒子非空，那就是第二类斯特林数 S(n, k)。一字之差，公式完全不同。我在带新人时发现，他们十个里有八个栽在这种“读题不仔细”的细节上，这比不会推导更可惜。

学习路径上，我比较推荐教材和题目穿插进行。书本方面《具体数学》和《组合数学》可以作为查阅工具，《算法竞赛进阶指南》里也有组合计数的实战章节。想真正内化，就应该把做过的计数题拿出来归类，总结哪几道题用的是同一个数学结构。等你有一天发现，写组合计数的状态转移和写普通递推差不多顺畅，那这个基础就算真正打牢了。