如果說組合計數里有什么技巧是最值得優先掌握的隔板法一定排在我心中的前三名。它的適用面廣、推導直觀、可以和不定方程、容斥原理、生成函數多個知識體系銜接而且在算法競賽里從入門的分球模型到后期復雜計數題你都會反復撞見它。你只需要記住一個核心公式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 生成函數隔板法的“算兩次”眼睛隔板法的非負整數解結論也可以用生成函數來表示。每個變量對應一個因子 1xx2x3...整個方程的系數就是解個數。具體來說把這些因子乘起來后x 的 n 次方系數就是 C(nm-1, m-1)。當題目要求某個變量必須是偶數、必須是質數、或者落在某個區間內時隔板法就抓瞎了但生成函數依然可以處理。比如 x1 要是偶數對應因子 1x2x?...x2 要在 [2,5] 內對應有限因子 x2x3x?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 往往更靠譜。組合計數這塊內容越往后學越會發現很多高級技巧都是在同一個思想框架下演變的。隔板法之所以值得花時間徹底吃透就是因為它處在分球模型和不定方程模型的交點上是通向容斥、生成函數、斯特林數的重要樞紐。我自己在實際刷題時最常用的一個檢查動作就是每套一個公式先代入最小數據集算一遍同時心里默念“球同、盒不同、可空還是非空”這個三問句。這三問句過關了隔板法的題基本就穩了。