如果说组合计数里有什么技巧是最值得优先掌握的隔板法一定排在我心中的前三名。它的适用面广、推导直观、可以和不定方程、容斥原理、生成函数多个知识体系衔接而且在算法竞赛里从入门的分球模型到后期复杂计数题你都会反复撞见它。你只需要记住一个核心公式n 个相同的小球放入 m 个不同的盒子每个盒子至少一个方案数是 C(n-1, m-1)。但如果你只背公式而不知道它为什么成立、边界条件是什么、怎么变形遇到稍拐弯的题目照样会翻车。这篇我就把隔板法从原理到变形再到实战踩坑一条龙讲透。1. 从“分球入盒”说起先搞懂隔板法最原始的模型1.1 两个隐藏得很深的前提条件隔板法最经典的表述是有 n 个完全相同的小球要放进 m 个不同的盒子里每个盒子至少有一个球问有多少种分配方案。很多新手第一眼会觉得这是个排列组合题但其实这里有两个隐含前提特别容易被忽略。第一个前提是球必须完全相同。球相同意味着第 i 个盒子里有几个球是唯一的关注点我们根本不关心“哪几个球”进去了。一旦球本身有编号、有颜色、有区分度题目性质就完全变了要换成容斥或者第二类斯特林数那套思路。比如把 3 个颜色不同的球放进 2 个不同的盒子且盒子不能为空答案是 2 的 3 次方减去 2也就是 6 种而如果球完全相同答案就只是 C(3-1, 2-1) 2 种即 (1,2) 和 (2,1) 两种分配。差别一目了然。第二个前提是盒子必须不同。盒子不同意味着“第一个盒子 3 个球、第二个盒子 2 个球”和“第一个盒子 2 个球、第二个盒子 3 个球”算两种不同方案。如果盒子长得一模一样那问题就退化成分拆数复杂程度直接上了一个台阶而且绝不能用隔板法结果简单除以 m! 来算。这点我在后面避坑章节会重点展开。判断一道题能不能用隔板法本质上就是在确认这两点小球被分配的对象是不是都等价、位置接收方是不是能被区分。如果题目描述里出现“把 k 个相同名额分给 n 个班级”“把 n 个相同任务分配给 m 台相同的服务器”那一多半就是隔板法的场景。1.2 为什么答案偏偏是 C(n-1, m-1)理解了前提之后我们来推导公式。把 n 个完全相同的小球在桌面上排成一排。想一想如果我想把它们分成 m 段每段至少一个小球我需要在球与球之间的空隙里插入隔板。n 个球排成一排它们中间只有 n-1 个空隙。要把球分成 m 个非空段需要放入 m-1 块隔板。每一块隔板占据一个空隙不同的隔板位置组合就对应不同的分配方案。于是问题瞬间变成一个纯粹的组合数问题从 n-1 个空隙中选出 m-1 个位置放隔板数量就是 C(n-1, m-1)。我用一个小例子验证一下。n5 个小球放进 m3 个盒子每个盒子非空。5 个球中间有 4 个空隙从中选 2 个空隙插板。直观枚举这 6 种方案113、122、131、212、221、311。我们用隔板法算一下C(4,2)6完全一致。这种“先排成一列再找空隙插板”的思路和高中排列组合里的“插空法”不太一样。插空法通常处理不相邻问题强调元素之间的间隔而隔板法处理的是分组问题强调把连续的同质元素切开。两者符号上都是选空隙但应用场景完全不同别搞混。1.3 为什么 n 个小球相同的核心是“只看数量不看个体”再往深挖一层隔板法本质上是把“分配方案”和“有序正整数数组”建立了一一对应。如果我构造一个数组 (x1, x2, ..., xm)其中 xi 表示第 i 个盒子分到的球数那么这个数组要满足两个条件每个 xi 都大于等于 1所有 xi 加起来等于 n。隔板法中的一个插板方案恰好对应一个这样的数组反过来任意一个满足条件的数组也能还原出唯一的插板位置。这就引出了一个极其重要的观点n 个相同球放入 m 个不同盒子且盒子非空的方案数和方程 x1x2...xmn 的正整数解个数是同一个数。这里“正整数解”指每个未知数都至少为 1。隔板法在这一刻从分球模型抽象成了数学方程模型而后者在算法题里出现的频率比“分球”高得多。2. 隔板法的三种常见变形一通百通2.1 盒子可以为空补球法的本质是偷换问题算法题里更多时候不会说“每个盒子至少一个”而是直接说“可以有空盒子”。比如把 n 个相同球放进 m 个不同盒子允许某些盒子空着这怎么算思路是先“假装”每个盒子都已经有 1 个球。于是现在一共有 nm 个球放进 m 个盒子每个盒子至少 1 个球的方案数就是 C(nm-1, m-1)。算完之后再从每个盒子里拿走 1 个球那些原本只有“假球”的盒子自然就空了。因为真实盒子里本来没有球拿走假球后变成空盒完全符合题意。换个角度看这个变形可以直接用不定方程x1x2...xmn每个 xi≥0 的非负整数解个数是 C(nm-1, m-1)。它与正整数解公式就差一个 m 的下标变化。很多考生容易在这里把式子记成 C(nm, m)我建议你用最小数据验证n1 个小球放 m2 个盒子允许空显然只有 2 种方案给第一个盒子或者给第二个盒子。C(12-1, 2-1)C(2,1)2 正确而 C(12,2)C(3,2)3 错误一下子就能筛掉记错的公式。2.2 每个盒子有“最低配额”先减掉再套模板有时候题目会加条件比如第 i 个盒子至少要放 ai 个球而且每个 ai 可能不一样。看起来比“至少一个”复杂但实际上只是做一次变量替换。设 xi 为第 i 个盒子实际分到的球数题目限制了 xi≥ai。我令 yi xi - ai这样 yi≥0且方程变成了 y1y2...ym n - (a1a2...am)。这个方程的非负整数解个数直接用 2.1 节的结论C(n - Σa m - 1, m-1)。这个变形特别适合处理“下界不为 1”的场景。比如 n20, m4要求第 1 个盒子至少 2 个第 2 个盒子至少 3 个后两个盒子至少 1 个那么 Σa 2311 7方程化为 y1...y4 13 的非负整数解答案是 C(134-1, 4-1) C(16,3)560。你不需要重新画隔板只需要把常量从 n 里扣掉。2.3 每个盒子有“最高配额”隔板法加容斥原理上界限制比下界限制麻烦一点因为没有哪一板能直接“剪掉超出的部分”。处理上界最标准的套路是容斥原理这也是隔板法真正体现威力的地方。设题目要求 0≤xi≤L其余条件照旧。先假装没有上界算出全集 C(nm-1, m-1)。然后减去那些“至少有一个变量超过 L”的方案。以第 i 个变量超过 L 为例即 xi≥L1。令 xi xi - (L1)剩下的 yi 仍是非负方程化为 xi Σ_{j≠i} xj n-(L1)方案数为 C(n-(L1)m-1, m-1)。用容斥把单个变量超限、两个变量同时超限等情况依次加减即可。通式写出来是Σ_{S⊆{1..m}} (-1)^{|S|} C(n - Σ_{i∈S}(L_i1) m - 1, m-1)其中如果 n - Σ(L_i1) 0则这一项记作 0。举个例子x1x2x310且每个 xi 都不超过 5求非负整数解个数。全集 C(103-1, 3-1) C(12,2)66。单个变量超限令 xi xi-6问题变为 xi另外两数 4方案 C(6,2)15。三个变量各自超限的情况都相同所以减去 3×1545。两个变量同时超限令 xi-6、xj-6方程变成 负的 2无解所以后续容斥项都是 0。最终答案是 66-4521。这个结果我很推荐你用枚举法再验证一遍能加深对容斥每一步“扣掉的是什么”的理解。3. 算法题视角三个等价模型背一张表胜过背十个题3.1 不定方程、隔板插空、组合分配三位一体隔板法最大的价值在于把三个看上去风马牛不相及的问题统一成了同一个数学模型。第一个模型是“n 个相同球放入 m 个不同盒子每个盒子非空”。第二个模型是“求 x1...xmn 的正整数解个数”。第三个模型是“从 n-1 个空隙里选 m-1 个放板”。它们之间是严格的等价关系。非空版本等价于正整数解、非空分盒、C(n-1, m-1)。 可空版本等价于非负整数解、允许空盒、C(nm-1, m-1)。在真实算法题里出题人从来不会直接写“分球”他会包装成各种样子。比如把 n 个相同的名额分给 m 个不同的社团允许某些社团没有名额这是非负整数解。求长度为 m 的递增且每个元素至少为 1 的正整数序列元素和为 n 的数量这是正整数解。把一份长度为 n 的区间分成 m 段非空子区间每段不能为空这是隔板插空。识别出题目本质是“把相同对象分给不同位置”之后所有问题都收敛到同一条公式上。这种识别能力比多会一个冷门技巧有用得多。3.2 从方程到实际的映射为什么解个数等于分球方案数有读者可能会问方程 x1x2x310 的解不可枚举也不直观凭什么说它和分球是一回事你想象把解写成 (2,3,5)那么它对应的是第一个盒子 2 个球、第二个盒子 3 个球、第三个盒子 5 个球。反过来任意一种分球方式读取每个盒子的球数就是一组解。因为盒子是有编号的所以解的顺序很重要这就是“正整数解”而不是“集合划分”的原因。这种一一对应关系形成之后你就可以放心地用隔板法的组合数结论去计算方程解个数而不用真的把所有解列出来。这其实也是组合计数思想的核心把抽象计数映射到我们已经掌握的模型上。3.3 一个综合应用区间分段问题来看一个很常见的编程题场景将长度为 n 的数组切成 m 段非空连续子数组问有多少种切法。一眼看上去像动态规划但仔细想n 个元素之间只有 n-1 个切缝要切出 m 段需要选 m-1 个切缝答案是 C(n-1, m-1)。这和“n 个球放 m 个盒子”完全同构。如果题目改成“可以切开但不要求每段都非空”也就是允许某些段长度为 0答案就变成 C(nm-1, m-1)。这里的 m-1 根隔板在极端情况下会相邻放产生空段。很多人在这一步反应不过来是因为总把问题想成“切数组”而不是“放隔板”。换个思路所有的隔板法其实只有一件事有多少个球决定空隙数量有多少个盒子决定需要多少隔板。至于可空不可空决定的是空隙数量在公式里要不要加上 m。4. 实操要点与避坑这部分我踩过的坑不止一次4.1 最大的坑球到底同不同我之前带过不少同学做组合计数题十个人里有三四个在处理含编号物品时直接套隔板法结果答案差得离谱。核心判断标准就一句话题目描述里参与分配的对象之间能不能互相替换。如果“把红球给甲”和“把蓝球给甲”是两种不同结果那球就是不同的不能用隔板法。比如有 n 个任务每个任务有不同名称分给 m 台机器允许机器空闲。每个任务独立选择机器答案应该是 m 的 n 次方。而如果任务是相同的、只有编号被抹去的副本答案才是隔板法的 C(nm-1, m-1)。这两个模型在实际业务场景中很常见弄混的结果不只是少一个常数而是整个计数逻辑错误。4.2 最大的坑盒子到底同不同另一个高频错误是把盒子也当成不加区分的。真正“盒子相同”的分配问题处理的是集合划分方案数不由简单组合数给出。举个例子n4 个相同球放 m2 个相同盒子非空方案只有 (1,3) 和 (2,2) 两种。你如果用隔板法算出 C(3,1)3再除以 2!得到 1.5毫无意义。因为隔板法枚举出的 (1,3) 与 (3,1) 在盒子相同的情况下是同一个方案但 (2,2) 不会重复。因此“除以盒子排列数”这种操作只在部分情况下碰巧正确不能当成通法。遇到盒子不区分的题目应当转向分拆数 p(n,m) 或者第二类斯特林数 S(n,m) 相关模型而不是硬套隔板法。4.3 组合数求值取模环境下怎么写代码算法竞赛中n 和 m 的范围经常会达到 1e5 甚至 1e6不能直接约分算浮点数。常规做法是预处理阶乘和阶乘逆元然后 O(1) 查询组合数。以 C 为例如果模数是 1e97 这类大质数可以用快速幂求逆元。先预处理 fac[0..maxn] 和 invfac[0..maxn]然后组合数就是 fac[n] * invfac[k] % MOD * invfac[n-k] % MOD。如果模数不是质数则不能用费马小定理求逆元得改用线性递推或者扩展欧几里得预处理。很多板子题卡的就是这个细节。隔板法公式里还容易出现一个下标陷阱C(n-1, m-1) 和 C(nm-1, m-1) 差了一个 m写代码前最好先用小数据验证一下。我自己的习惯是在函数里封装一个 C(n,k) 并自动处理 k 越界返回 0 的情况这样即使 n-(L1) 变成负数也不会导致数组访问越界而是直接返回 0容斥代码会清爽很多。4.4 心算验证小技巧任何隔板法公式得到的结果我强烈建议先挑最小参数手工验证。比如 n5, m3我会在草稿纸上把 6 种拆法写出来113、122、131、212、221、311确认没有遗漏也没有重复。一旦题目带上了界限制就验证 n3, m2, 每个变量 0≤xi≤2。全集是 4减去超限的情况 2答案是 2也就是 (0,3) 和 (3,0) 这两组被排除后剩下的 (1,2) 和 (2,1)。这种小数据验证能在十秒内揪出公式错误。5. 几道完整实战题彻底打通隔板法的使用链路5.1 经典变式每人至少两个且总量固定题目把 10 个完全相同的苹果分给 3 个小朋友每个小朋友至少 2 个苹果有多少种分法直接把条件翻译成不定方程x1x2x310, xi≥2。令 yixi-2方程化为 y1y2y34, yi≥0。套可空模型答案 C(43-1, 3-1) C(6,2)15。有的同学会试图把“至少 2 个”转化成“至少 1 个”后继续用隔板但更朴素的思路就是先扣减下限剩下的部分再当作非负分配。后者能避免很多混乱。5.2 上下界同时存在隔板法和容斥的配合题目把 10 个完全相同的苹果分给 3 个小朋友每人至少 1 个但第一个小朋友最多拿 5 个问有多少种分法设 x1x2x310, xi≥1, x1≤5。先减下限令 yixi-1则 y1y2y37, yi≥0, y1≤4。全集C(73-1, 3-1) C(9,2)36。 考虑 y1 超限的情况y1≥5令 y1y1-5方程化为 y1y2y32方案 C(4,2)6。 其他变量没有上界不需要容斥。 最终答案 36-630。这个题你可以尝试枚举验证把 (x1,x2,x3) 按 x1 从 1 到 5 枚举会发现和恒为 10 且每个数至少 1 的组合正好 30 组说明容斥没有多减。5.3 多个上界容斥公式的完整展开题目求 x1x2x3x412 的非负整数解个数且 x1≤3, x2≤4, x3≤5, x4≤6。全集C(124-1,4-1)C(15,3)455。 单个变量超限若 x1≥4令 x1x1-4方程变为 x1x2x3x48方案 C(11,3)165。类似地x2 超限需要减去 516方程变为 12-66方案 C(9,3)84x3 超限减 6方程变为 6方案 C(9,3)84x4 超限减 7方程变为 5方案 C(8,3)56。 先减去单变量超限的总和455-(165848456)66。 两个变量同时超限x1 与 x2 同时超限需要减 459方程变为 12-93方案 C(6,3)20。类似地算 x1,x3 同超限、x1,x4 同超限、x2,x3 同超限、x2,x4 同超限、x3,x4 同超限得到 20、20、C(2,3)0、C(5,3)10、C(4,3)4、C(3,3)1总和 55。 加回这些6655121。 三个变量同时超限x1,x2,x3 同时超限12-(67?) 我算的时候发现负数贡献 0其余组合也类似为 0。所以最终答案 121。这种多上界问题在数学题里属于竞赛难度但在算法题里反而常见因为代码实现时只需要一个位掩码枚举子集再调用组合数函数几乎不需要人肉展开。5.4 用位掩码实现通用容斥伪代码思路大概是long long countSolutions(int n, int m, vectorint low, vectorint high) { // 先处理下界令 n n - sum(low) // 再对 high 在减去 low 后的上限做容斥 long long ans 0; for (int mask 0; mask (1 m); mask) { int s 0, bits 0; for (int i 0; i m; i) if (mask i 1) { s high[i] 1; bits; } if (n - s 0) continue; if (bits 1) ans - C(n - s m - 1, m - 1); else ans C(n - s m - 1, m - 1); } return ans; }这里的 high[i] 指的是变量被约束为 xi≤high[i]。下界处理完以后一切回到标准的非负整数解模型。代码里的组合数函数必须能处理 k0 或 kn 的情况直接返回 0。6. 从隔板法出发还能延伸到哪些更高阶的工具6.1 生成函数隔板法的“算两次”眼睛隔板法的非负整数解结论也可以用生成函数来表示。每个变量对应一个因子 1xx²x³...整个方程的系数就是解个数。具体来说把这些因子乘起来后x 的 n 次方系数就是 C(nm-1, m-1)。当题目要求某个变量必须是偶数、必须是质数、或者落在某个区间内时隔板法就抓瞎了但生成函数依然可以处理。比如 x1 要是偶数对应因子 1x²x⁴...x2 要在 [2,5] 内对应有限因子 x²x³x⁴x⁵。把所有因子乘起来找系数本质就是多项式卷积。这也是我建议学完隔板法后顺手补一下生成函数的原因两者承接得非常自然。6.2 球盒模型全家桶隔板法是“球相同、盒不同”这一格的答案但组合计数里的球盒模型一共有六种基本情况。我把它们列成一张表方便对照记忆球盒子是否允许空盒计数方式相同不同非空C(n-1, m-1)相同不同允许空C(nm-1, m-1)不同不同非空m! * S(n,m)或用容斥不同不同允许空m^n相同相同非空分拆数 p(n,m)不同相同非空第二类斯特林数 S(n,m)不同相同允许空Bell 数这张表建议刻进脑子里。很多计数题的本质就是把题面翻译成“哪一格”翻译对了直接用公式或递推翻译错了后面全白搭。6.3 与动态规划的取舍有时候一个计数题既能用 DP 又能用隔板法。比如“把 n 个相同物品分给 m 个人每人至少一个”DP 是 O(nm)而隔板法是 O(1) 或 O(m) 组合数查询。当 n 和 m 都到 1e5 时DP 直接不可行组合数就体现出压倒性优势。但反过来如果题目加上了类似“相邻盒子之间球数必须满足某种大小关系”这种复杂限制隔板法和容斥会变得极其繁琐此时退回到 DP 反而是更稳的选择。我自己的经验是先看限制条件能不能被转换成“变量的下界/上界/等量替换”如果能就放心用隔板法如果限制涉及到变量之间的相对关系DP 往往更靠谱。组合计数这块内容越往后学越会发现很多高级技巧都是在同一个思想框架下演变的。隔板法之所以值得花时间彻底吃透就是因为它处在分球模型和不定方程模型的交点上是通向容斥、生成函数、斯特林数的重要枢纽。我自己在实际刷题时最常用的一个检查动作就是每套一个公式先代入最小数据集算一遍同时心里默念“球同、盒不同、可空还是非空”这个三问句。这三问句过关了隔板法的题基本就稳了。