到多項式求解：容斥與生成函數(shù)的算法實踐)
1. 問題引入與核心思路拆解看到“Yet Another Permutation Problem”這個標題很多搞過組合數(shù)學或者算法競賽的朋友可能會心一笑——這又是一個關(guān)于排列的計數(shù)問題。這類問題在LOJLibreOJ這樣的在線評測系統(tǒng)里尤其是集訓隊作業(yè)中可以說是家常便飯。但別被這個看似普通的標題騙了后綴括號里的“容斥生成函數(shù)多項式”已經(jīng)暗示了它的分量。這絕對不是一道讓你手算幾個小規(guī)模排列數(shù)就能解決的題目它考察的是如何將復雜的組合約束通過一系列經(jīng)典的組合工具轉(zhuǎn)化成一個可以高效計算的數(shù)學模型。我拿到這個題的第一反應是去理解它到底在問什么。通常這類“Yet Another”問題會在經(jīng)典排列問題上增加一些新的、奇怪的限制條件。比如可能要求排列中某些位置必須大于其相鄰位置即“峰”或“谷”或者要求某些數(shù)字對必須滿足特定的大小關(guān)系。這道題的具體描述雖然輸入中未給出但根據(jù)經(jīng)驗和關(guān)鍵詞可以推斷很可能涉及對排列中“逆序?qū)Α?、“上升序列”或某種“模式”出現(xiàn)次數(shù)的限制。問題的核心挑戰(zhàn)在于直接枚舉所有排列并檢查條件在n稍大時比如n1000是完全不可能的我們需要一個能在多項式時間內(nèi)通常是O(n log n)或O(n^2)計算出答案的解析方法或算法。那么標題中給出的工具鏈“容斥 - 生成函數(shù) - 多項式”就是解決此類問題的標準“組合套餐”。容斥原理是我們處理“至少”或“恰好”滿足某些條件計數(shù)的利器它能把復雜的交集條件轉(zhuǎn)化為更簡單的補集運算。生成函數(shù)尤其是普通生成函數(shù)OGF和指數(shù)生成函數(shù)EGF則是將組合對象如排列和計數(shù)序列轉(zhuǎn)化為代數(shù)對象的魔法它允許我們使用代數(shù)運算如乘法、求逆、復合來代替復雜的組合推理。最后多項式則是承載生成函數(shù)的容器問題的答案往往就是某個多項式的某一項系數(shù)而我們需要通過多項式運算如卷積、求逆、exp/ln來高效地計算出這個系數(shù)。接下來我會按照“理解約束 - 容斥轉(zhuǎn)化 - 生成函數(shù)建模 - 多項式求解”這條主線一步步拆解這個問題的通用解法思路并分享在實現(xiàn)過程中容易踩坑的細節(jié)。即使你之前對生成函數(shù)有些發(fā)怵我相信通過這個具體問題的牽引你也能感受到這套組合工具的威力與美感。1.1 從排列約束到容斥框架第一步也是最關(guān)鍵的一步是把題目中那些關(guān)于排列的、難以直接處理的條件轉(zhuǎn)化成一個可以用容斥原理處理的邏輯形式。我們假設(shè)題目要求排列p[1..n]滿足k個限制條件每個條件可能形如“數(shù)字i不能出現(xiàn)在位置j”或者“數(shù)字a必須排在數(shù)字b之前”甚至是更復雜的“不存在長度為3的下降子序列”。直接計算滿足所有條件的排列數(shù)非常困難。容斥原理提供了一個框架滿足所有條件的排列數(shù) 總排列數(shù) - 至少違反一個條件的排列數(shù) 至少違反兩個條件的排列數(shù) - ...。這里“違反條件”通常比“滿足條件”更容易刻畫。例如如果條件是“數(shù)字i不能出現(xiàn)在位置j”那么“違反”這個條件就意味著“數(shù)字i恰好出現(xiàn)在位置j”這實際上固定了一個位置剩下的部分就是一個(n-1)的排列很容易計算。因此我們的策略是定義一組“壞事件”A1, A2, ..., Am每個壞事件對應違反了某個或某組原始條件。利用容斥原理答案 Σ_{S ? [m]} (-1)^{|S|} * (同時違反S中所有壞事件的排列數(shù))。計算“同時違反S中所有壞事件”的排列數(shù)。如果這些壞事件涉及的約束是獨立的比如固定了若干個互不相同的位置那么這個數(shù)就是(n - |S|)!。如果約束間有沖突比如要求同一個位置放兩個不同的數(shù)那么計數(shù)為0。在實際問題中壞事件的設(shè)計需要技巧。有時我們需要對“違反條件”的程度進行更精細的劃分比如不是簡單地“違反”而是“違反至少t次”這可能會引入新的求和指標。這時生成函數(shù)就能很好地幫我們管理這些指標。1.2 生成函數(shù)將組合結(jié)構(gòu)轉(zhuǎn)化為代數(shù)方程當我們用容斥原理寫出一個帶多重求和的表達式后生成函數(shù)就能大顯身手了。它的核心思想是把一個序列a_0, a_1, a_2, ...包裝成一個形式冪級數(shù)A(x) Σ a_i * x^i。這里的x只是一個形式符號它的指數(shù)i通常代表我們關(guān)心的某個組合量如違反條件的次數(shù)、選取的元素個數(shù)等。為什么這樣做有用因為冪級數(shù)的運算規(guī)則加法、乘法、復合恰好對應了組合結(jié)構(gòu)的合并、拼接、選擇等操作。例如乘法如果A(x)計數(shù)“完成任務甲”的方式數(shù)任務甲有i種方式則貢獻a_i * x^iB(x)計數(shù)“完成任務乙”的方式數(shù)那么A(x) * B(x)的系數(shù)就計數(shù)了“先獨立完成甲再獨立完成乙”的所有方式數(shù)并且總“量”是兩者之和。這在組合中稱為卷積。指數(shù)生成函數(shù)EGF專門用于處理帶標號對象的計數(shù)比如排列。排列的EGF是Σ_{n0} n! / n! * x^n Σ x^n 1/(1-x)。但更重要的是當我們用EGF表示一個“結(jié)構(gòu)”時其乘法對應了標號集合的合并與重排這非常適合處理排列問題。在這道題中我們很可能會構(gòu)造一個生成函數(shù)F(x)其中[x^k] F(x)即x^k的系數(shù)代表了與“違反條件”的某種度量相關(guān)的計數(shù)。通過容斥原理最終的答案可以表示為對這個生成函數(shù)進行一系列運算如求1 - F(x)的某種變換后提取x^n系數(shù)或代入x1等操作的結(jié)果。1.3 多項式科技從生成函數(shù)到可計算系數(shù)生成函數(shù)給出了一個優(yōu)美的封閉形式但我們的最終目標是要一個具體的數(shù)字——通常是這個生成函數(shù)某一項的系數(shù)。這時就需要“多項式科技”了。我們通常只能在模一個質(zhì)數(shù)如998244353,1000000007的意義下進行計算因為這些質(zhì)數(shù)域存在原根支持快速數(shù)論變換NTT從而能在O(n log n)時間內(nèi)完成多項式乘法、求逆、exp、ln等操作。整個解題過程可以看作一個多項式計算流水線建立模型根據(jù)容斥原理推導出答案的生成函數(shù)表達式。多項式表示將生成函數(shù)F(x)截斷到n次因為高于n次的項對答案無貢獻用長度為O(n)的多項式系數(shù)數(shù)組來表示它。多項式運算按照表達式對多項式進行一系列運算。常見的操作包括乘法/卷積對應獨立事件的組合。求逆求解1 / (1 - F(x))這類形式。指數(shù)函數(shù)Exp當我們需要計算“將若干個不可區(qū)分的組件組合起來”時EGF的Exp會出現(xiàn)。對數(shù)函數(shù)Ln常與Exp配對出現(xiàn)用于解耦。提取系數(shù)從最終得到的多項式G(x)中取出x^n的系數(shù)或者根據(jù)題意可能是對系數(shù)進行求和即為答案。這個過程將組合推理完全轉(zhuǎn)化為了代數(shù)計算使得我們能夠處理規(guī)模很大的n例如n10^5這是暴力枚舉或動態(tài)規(guī)劃無法企及的。2. 一個具體模型帶禁止位置的排列問題為了讓大家更有體感我們不妨用一個經(jīng)典的、與題目可能相關(guān)的模型來具體演練一下這套流程計算恰好有k個位置滿足p_i i的排列數(shù)即恰好有k個不動點。這個問題被稱為“錯位排列”的推廣。雖然原題可能更復雜但這個例子涵蓋了容斥、生成函數(shù)和多項式的基本運用。2.1 容斥原理推導設(shè)A_i為事件“數(shù)字i放在位置i”即它是一個不動點違反了“錯位”的要求?？偱帕袛?shù)n!。至少有一個不動點的排列數(shù)Σ |A_i| C(n,1)*(n-1)!。至少有兩個不動點的排列數(shù)Σ |A_i ∩ A_j| C(n,2)*(n-2)!其中ij?！辽儆衪個不動點的排列數(shù)C(n, t) * (n-t)!。根據(jù)容斥原理沒有不動點的排列數(shù)即經(jīng)典錯排數(shù)D_n為D_n Σ_{t0}^{n} (-1)^t * C(n, t) * (n-t)! n! * Σ_{t0}^{n} (-1)^t / t!。而我們要求的是恰好有k個不動點的排列數(shù)。這可以理解為先選定k個位置作為不動點有C(n, k)種選法然后剩下的n-k個位置必須形成一個無不動點的排列即錯排。因此答案Ans_k為Ans_k C(n, k) * D_{n-k} C(n, k) * (n-k)! * Σ_{t0}^{n-k} (-1)^t / t!。這個公式已經(jīng)可以計算了。但如果我們想為所有k0..n一次性求出Ans_k或者n很大這個求和式的計算就顯得有些孤立。這時生成函數(shù)可以提供更統(tǒng)一的視角。2.2 生成函數(shù)建模我們嘗試構(gòu)造一個生成函數(shù)使其x^k的系數(shù)與Ans_k相關(guān)。觀察公式Ans_k C(n, k) * (n-k)! * Σ_{t0}^{n-k} (-1)^t / t!。 令a_m m! * Σ_{t0}^{m} (-1)^t / t!那么Ans_k C(n, k) * a_{n-k}。我們知道數(shù)列C(n, k)的生成函數(shù)是(1x)^n。而數(shù)列a_m的指數(shù)生成函數(shù)EGFA(x)是什么a_m m! * [x^m] ( Σ_{t0} (-1)^t / t! * x^t )不對因為求和上限是m不是無窮。這提示我們a_m其實是m!與錯排數(shù)D_m的卷積讓我們重新審視。實際上D_m m! * Σ_{t0}^{m} (-1)^t / t!。所以a_m D_m。 那么Ans_k C(n, k) * D_{n-k}?，F(xiàn)在考慮二元生成函數(shù)F(x, y)我們希望[x^n y^k] F(x, y)正比于Ans_k。這不容易直接構(gòu)造。更常見的做法是固定n為序列{Ans_k}構(gòu)造一個普通生成函數(shù)OGF。對于固定的n定義G_n(z) Σ_{k0}^{n} Ans_k * z^k。 將Ans_k C(n, k) * D_{n-k}代入G_n(z) Σ_{k0}^{n} C(n, k) * D_{n-k} * z^k Σ_{j0}^{n} C(n, n-j) * D_j * z^{n-j}令j n-k Σ_{j0}^{n} C(n, j) * D_j * z^{n-j}。這個形式還不夠漂亮。我們利用D_j的EGF。已知錯排數(shù)的EGF是D(x) Σ_{j0} D_j / j! * x^j e^{-x} / (1-x)。 那么G_n(z)可以寫成G_n(z) z^n * Σ_{j0}^{n} C(n, j) * (D_j / j!) * (j!) * z^{-j} 這樣處理起來很麻煩。一個更聰明的辦法是回到容斥的源頭。定義生成函數(shù)H(t)其中[t^s] H(t)表示至少有s個不動點的排列數(shù)。根據(jù)容斥我們知道H(t) Σ_{s0}^{n} (至少s個不動點的排列數(shù)) * t^s。 而“至少s個不動點”的排列數(shù)等于先選s個位置作為不動點C(n, s)然后剩下n-s個位置任意排列(n-s)!。所以H(t) Σ_{s0}^{n} C(n, s) * (n-s)! * t^s Σ_{s0}^{n} n! / s! * t^s。那么恰好有k個不動點的排列數(shù)就是[t^k] H(t-1)。這是因為容斥原理在生成函數(shù)中的體現(xiàn)就是代入-1進行“符號交替”。我們可以驗證H(t-1) Σ_{s0}^{n} n! / s! * (t-1)^s Σ_{s0}^{n} n! / s! * Σ_{k0}^{s} C(s, k) * t^k * (-1)^{s-k}交換求和順序[t^k] H(t-1) Σ_{sk}^{n} n! / s! * C(s, k) * (-1)^{s-k} n! / k! * Σ_{sk}^{n} (-1)^{s-k} / (s-k)! n! / k! * Σ_{t0}^{n-k} (-1)^t / t! C(n, k) * (n-k)! * Σ_{t0}^{n-k} (-1)^t / t! Ans_k。完美所以我們得到了一個簡潔的生成函數(shù)表達式Ans_k [t^k] Σ_{s0}^{n} n! / s! * (t-1)^s。2.3 多項式計算實現(xiàn)現(xiàn)在我們要計算G(t) Σ_{s0}^{n} n! / s! * (t-1)^s這個多項式然后取出它的各個系數(shù)。這完全是一個多項式運算問題。構(gòu)造多項式令F(x) Σ_{s0}^{n} (n! / s!) * x^s。這是一個簡單的多項式系數(shù)a_s n! / s!。多項式平移我們需要計算G(t) F(t-1)。這等價于計算F(x)在x t-1處的值。多項式平移可以通過卷積來實現(xiàn)。設(shè)F(x) Σ a_i x^i則F(xc) Σ a_i (xc)^i Σ a_i Σ_{j0}^{i} C(i,j) c^{i-j} x^j。交換求和順序后這可以寫成兩個序列的卷積b_j a_j * j!和c_{i-j} c^{i-j} / (i-j)!的卷積結(jié)果再除以j!。這就是經(jīng)典的多項式“泰勒平移”算法利用卷積和階乘預處理可以在O(n log n)時間內(nèi)完成。提取系數(shù)平移后得到的多項式G(t)的系數(shù)[t^k] G(t)就是我們要求的Ans_k。在實際代碼實現(xiàn)中以模998244353為例步驟如下#include bits/stdc.h using namespace std; const int mod 998244353, G 3; // NTT模數(shù)與原根 // 此處省略NTT多項式乘法、求逆等模板代碼... vectorint solve_fixed_point(int n) { // 1. 預處理階乘和逆元 vectorint fac(n1), ifac(n1); fac[0] 1; for(int i1; in; i) fac[i] 1LL * fac[i-1] * i % mod; ifac[n] powmod(fac[n], mod-2); for(int in; i1; i--) ifac[i-1] 1LL * ifac[i] * i % mod; // 2. 構(gòu)造多項式 F(x) Σ_{s0..n} (n! / s!) * x^s vectorint F(n1); for(int s0; sn; s) { F[s] 1LL * fac[n] * ifac[s] % mod; // n! / s! } // 3. 計算 G(t) F(t-1)使用多項式平移算法 // 多項式平移已知 F(x) Σ a_i x^i, 求 F(xc) 的各項系數(shù) // 算法令 A[i] a_i * i! , B[j] c^j / j! // 計算 C A * B (卷積), 則 F(xc) 的系數(shù) coeff_k C[k] / k! int c mod - 1; // c -1 vectorint A(n1), B(2*n1); for(int i0; in; i) A[i] 1LL * F[i] * fac[i] % mod; int pow_c 1; for(int j0; j2*n; j) { B[j] 1LL * pow_c * ifac[j] % mod; pow_c 1LL * pow_c * c % mod; } vectorint C multiply(A, B); // 多項式乘法使用NTT長度需處理 vectorint G(n1); for(int k0; kn; k) { G[k] 1LL * C[k] * ifac[k] % mod; } // G[k] 現(xiàn)在就是恰好有k個不動點的排列數(shù) Ans_k return G; }注意這里的多項式平移算法是標準做法但需要注意卷積后數(shù)組的長度只取前n1項。multiply函數(shù)是封裝好的NTT卷積。通過這個例子我們看到了如何將一個具體的排列計數(shù)問題恰好k個不動點通過容斥原理轉(zhuǎn)化為生成函數(shù)表達式最終落地為多項式平移的計算。原題“LOJ3395”的約束條件肯定比“不動點”更復雜可能涉及逆序?qū)Α⑸仙蛄械鹊浜诵姆椒ㄕ撌窍嗤ǖ亩x合適的“壞事件”應用容斥用生成函數(shù)整合容斥系數(shù)最后用多項式科技快速計算。3. 擴展到更一般的排列約束問題現(xiàn)在讓我們把思路從具體的“不動點”問題抽離回到“Yet Another Permutation Problem”可能涵蓋的更一般情形。常見的排列約束包括局部大小關(guān)系例如要求對于所有i有p_i p_{i1}上升或p_i p_{i1}下降在某些特定位置成立。模式避免要求排列中不出現(xiàn)特定的模式如3,1,2這種子序列?；谥档臈l件例如p_i必須是i的倍數(shù)或者|p_i - i|在一定范圍內(nèi)。對于這類問題一個強大的工具是多項式插值或動態(tài)規(guī)劃與生成函數(shù)的結(jié)合。思路是先設(shè)計一個關(guān)于某個參數(shù)k的動態(tài)規(guī)劃DP求出當參數(shù)為k時的答案f(k)。如果我們可以證明f(k)是一個關(guān)于k的、次數(shù)不超過n的多項式那么我們就可以通過計算f(0), f(1), ..., f(n)這n1個點值然后利用多項式插值拉格朗日插值求出f(k)的多項式表達式進而可以快速求出任意k對應的值。3.1 動態(tài)規(guī)劃設(shè)計與多項式證明如何設(shè)計這樣的DP考慮一個經(jīng)典的例子計算有多少個n的排列其最長上升子序列LIS長度恰好為k。直接計算是困難的。但我們可以計算有多少個排列其LIS長度不超過k。記這個數(shù)為g(k)。那么答案就是g(k) - g(k-1)。如何計算g(k)這需要用到Robinson-Schensted correspondenceRSK對應它建立了排列與楊表Young Tableau之間的一一對應。而一個排列的LIS長度等于其對應的楊表的第一行的長度。標準楊表的形狀是一個整數(shù)分拆λ ? n且第一行長度不超過k的楊表數(shù)量可以由鉤子公式Hook-length Formula給出。對所有滿足λ_1 k的分拆求和可以得到g(k)?？梢宰C明g(k)是關(guān)于k的多項式函數(shù)在k n時是常數(shù)n!。另一個常見的DP狀態(tài)設(shè)計是按值域從小到大插入數(shù)字。設(shè)dp[i][j]表示考慮了1..i這些數(shù)字構(gòu)成的排列實際上是{1..i}的一個排列滿足某種約束的狀態(tài)為j時的方案數(shù)。當插入下一個數(shù)字i1時我們考慮它可以插入的位置并分析狀態(tài)j如何轉(zhuǎn)移。如果狀態(tài)j的定義是“當前有多少個違反條件的位置”或者“當前已經(jīng)形成的某種模式的數(shù)量”那么最終我們關(guān)心的f(k) Σ_{j} dp[n][j]其中求和可能只針對特定的j如jk也可能需要容斥求和。證明f(k)是k的多項式通常需要分析DP轉(zhuǎn)移方程。如果轉(zhuǎn)移方程中只包含k的加減、乘法而不包含除法在模意義下除法可能對應乘法逆元但多項式性可能被破壞并且循環(huán)次數(shù)固定那么f(k)很可能是一個多項式。一個實用的判斷是如果我們可以將DP過程看作是在一個固定大小的圖上進行固定步數(shù)的游走每條邊的權(quán)重是k的多項式那么最終的結(jié)果就是k的多項式。3.2 多項式插值計算一旦我們確定f(k)是次數(shù)不超過D的多項式通常D O(n)并且我們有能力在O(D)或O(D log D)時間內(nèi)計算出f(0), f(1), ..., f(D)這D1個點值那么我們就可以通過插值得到這個多項式。拉格朗日插值公式f(x) Σ_{i0}^{D} f(i) * Π_{j≠i} (x - j) / (i - j)。直接計算的復雜度是O(D^2)。但我們可以優(yōu)化到O(D log D)預處理所有(x - j)的乘積P(x) Π_{j0}^{D} (x - j)。對于每個i計算P(i) Π_{j≠i} (i - j)。這可以通過預處理階乘得到P(i) (i)! * (-1)^{D-i} * (D-i)!。那么f(x) P(x) * Σ_{i0}^{D} f(i) / ( (x-i) * P(i) )。如果我們只需要求一個點值x K那么用這個公式計算是O(D)的。如果我們需要恢復整個多項式系數(shù)就需要用到多項式多點求值、快速插值等更高級的算法復雜度O(D log^2 D)。在實際解題如LOJ3395時我們可能不需要顯式求出整個多項式而是直接利用插值公式計算題目所要求的特定k對應的f(k)。3.3 綜合應用一道模擬賽題的思路假設(shè)有這樣一道題求n的排列中滿足“不存在長度大于等于k的連續(xù)下降子串”的排列數(shù)量。例如對于n4, k3排列[3,2,1,4]是無效的因為它有連續(xù)下降子串[3,2,1]長度為3。我們可以這樣思考容斥用總排列數(shù)n!減去存在至少一個長度k的連續(xù)下降子串的排列數(shù)。但“至少一個”不好直接算因為子串可能重疊。轉(zhuǎn)化考慮排列的“下降塊”劃分。將一個排列劃分成若干個極長的連續(xù)下降子串。例如[4,3,1,2,5]可以劃分成[4,3,1]和[2,5]。要求每個下降塊的長度都 k。生成函數(shù)一個長度為L的下降塊其內(nèi)部只有一種排列方式嚴格遞減。但是這些塊在排列中是有順序的并且塊與塊之間前一個塊的最后一個元素與后一個塊的第一個元素構(gòu)成一個上升關(guān)系。這有點像將n個元素劃分成一些有序的“盒子”每個盒子大小k盒子內(nèi)部強制遞減。DP與多項式設(shè)dp[i]表示i個元素組成若干下降塊每個塊長度k的方案數(shù)。轉(zhuǎn)移時枚舉最后一個塊的長度j (1jk)則dp[i] dp[i-j]因為最后一個塊確定后前面的i-j個元素任意排。初始dp[0]1。我們要求的是dp[n]。但注意這dp[n]計算的是“將n個元素分成若干下降塊”的方案數(shù)每個方案對應一個唯一的排列嗎是的因為塊內(nèi)遞減順序固定塊間順序就是這些塊在排列中的出現(xiàn)順序。但這里我們忽略了塊間元素的相對大小實際上當我們用1..i的數(shù)字時dp[i]計數(shù)的是滿足塊結(jié)構(gòu)的所有排列數(shù)?？梢宰C明這個DP是正確的。生成函數(shù)優(yōu)化這個DP的生成函數(shù)D(x) Σ dp[i] x^i滿足D(x) 1 (x x^2 ... x^{k-1}) * D(x)。所以D(x) 1 / (1 - (x x^2 ... x^{k-1}))。那么dp[n] [x^n] 1/(1 - (xx^2...x^{k-1}))。這個系數(shù)可以用多項式求逆在O(n log n)時間內(nèi)得到。你看通過將問題重新解釋為“下降塊劃分”我們繞開了復雜的容斥直接得到了一個簡潔的生成函數(shù)。這展示了組合視角轉(zhuǎn)化的重要性。原題LOJ3395很可能也需要類似的、更巧妙的組合解釋。4. 實戰(zhàn)中的常見陷阱與優(yōu)化技巧即使思路正確在實現(xiàn)這類涉及容斥、生成函數(shù)和多項式的問題時也有很多細節(jié)容易出錯。下面分享一些我踩過坑后總結(jié)的經(jīng)驗。4.1 容斥系數(shù)與符號處理這是最容易出錯的地方之一。容斥原理的符號是(-1)^{|S|}其中|S|是違反條件的集合大小。但在生成函數(shù)中我們可能會將違反條件的“次數(shù)”作為指數(shù)。例如在“不動點”問題中我們構(gòu)造了H(t) Σ_{s} (至少s個不動點的方案數(shù)) * t^s然后通過H(t-1)得到“恰好”的計數(shù)。這里(t-1)^s展開后t^k項的系數(shù)天然就包含了C(s, k) * (-1)^{s-k}這個容斥系數(shù)。關(guān)鍵檢查點當你的生成函數(shù)代表“至少”或“欽定”某種情況時代入-1或更一般的使用(1-z)的冪往往能實現(xiàn)“恰好”的轉(zhuǎn)換。務必用小數(shù)據(jù) (n1,2,3) 手動驗證你的生成函數(shù)表達式。計算幾個系數(shù)看看是否符合暴力枚舉的結(jié)果。4.2 多項式運算的邊界與長度進行多項式乘法、求逆、exp/ln時必須明確你需要保留的次數(shù)。例如在計算[x^n] 1/(1 - A(x))時如果A(x)的次數(shù)是m那么1/(1-A(x))的x^n項系數(shù)可能依賴于A(x)的更高次項嗎不會因為這是一個無限級數(shù)但在模x^{n1}的意義下計算就足夠了。所以我們通常在模x^{M}的意義下進行多項式運算其中M是所需的最大次數(shù)加一。常見錯誤多項式乘法后結(jié)果數(shù)組長度應該是len(A)len(B)-1但如果你只關(guān)心前n項可以只保留前n1項以節(jié)省計算量和內(nèi)存。多項式求逆、exp、ln等操作要求初始多項式的常數(shù)項滿足特定條件如求逆要求常數(shù)項非零exp要求常數(shù)項為0。在執(zhí)行這些操作前務必檢查。4.3 模運算下的除法與階乘組合計數(shù)通常涉及大量的階乘n!和組合數(shù)C(n, k)。在模質(zhì)數(shù)P下我們需要預處理階乘fac[i]和階乘的逆元ifac[i]。這樣C(n, k) fac[n] * ifac[k] % P * ifac[n-k] % P。注意事項預處理數(shù)組的長度至少要開到n的最大可能值通常還會多開一點如n5以防越界。當公式中出現(xiàn)除法時如1/s!在模運算下必須乘以s!的乘法逆元。永遠不要直接做除法。4.4 時間復雜度的分析與優(yōu)化這類問題的典型時間復雜度是O(n log n)或O(n log^2 n)取決于多項式運算的復雜度。NTT的卷積是O(n log n)。多項式求逆、exp、ln可以通過牛頓迭代法在O(n log n)內(nèi)完成。優(yōu)化點減少多項式運算次數(shù)有時表達式可以化簡。例如exp(A(x)) * exp(B(x)) exp(A(x)B(x))先做加法再做一次exp比做兩次exp再卷積要快。利用對稱性如果生成函數(shù)是偶數(shù)函數(shù)或奇數(shù)函數(shù)可能可以簡化計算。分治NTT如果DP轉(zhuǎn)移是dp[i] Σ_{j i} dp[j] * a[i-j]這種形式且a已知那么這就是一個標準的卷積可以用NTT一次算出。如果轉(zhuǎn)移方程更復雜可能需要分治NTT將復雜度從O(n^2)降為O(n log^2 n)。4.5 調(diào)試與對拍這類題目調(diào)試起來比較困難因為中間結(jié)果多項式系數(shù)往往很長。我的調(diào)試策略是小數(shù)據(jù)暴力寫一個O(n! * n)的暴力程序枚舉所有排列并檢查條件計算n8時的答案。用這個來驗證你的多項式程序在小數(shù)據(jù)下的結(jié)果。中間輸出將關(guān)鍵步驟的多項式前幾項系數(shù)打印出來與手算或另一種思路的計算結(jié)果對比。例如計算“至少s個不動點”的生成函數(shù)H(t)你可以手動計算n4時H(t)的系數(shù)與程序輸出對比。對拍如果題目有部分分比如n20用暴力程序跑部分分用多項式程序跑全部數(shù)據(jù)在交叉部分n20驗證答案是否一致。靜態(tài)查錯仔細檢查容斥的符號、生成函數(shù)中變量的意義是指數(shù)還是普通系數(shù)、多項式運算的長度、模運算的正確性。處理這類問題就像在搭建一個精密的儀器。容斥原理是設(shè)計圖生成函數(shù)是傳動系統(tǒng)多項式算法是加工工具。任何一個環(huán)節(jié)的微小誤差都可能導致最終結(jié)果謬以千里。但一旦你成功搭建起來看到對于n100000的規(guī)模也能在秒級內(nèi)計算出答案那種成就感是無與倫比的。它讓你真正體會到組合數(shù)學不僅僅是巧妙的計數(shù)更是可以將復雜問題轉(zhuǎn)化為可計算模型的強大數(shù)學框架。 從排列計數(shù)到多項式求解：容斥與生成函數(shù)的算法實踐
1. 問題引入與核心思路拆解看到“Yet Another Permutation Problem”這個標題很多搞過組合數(shù)學或者算法競賽的朋友可能會心一笑——這又是一個關(guān)于排列的計數(shù)問題。這類問題在LOJLibreOJ這樣的在線評測系統(tǒng)里尤其是集訓隊作業(yè)中可以說是家常便飯。但別被這個看似普通的標題騙了后綴括號里的“容斥生成函數(shù)多項式”已經(jīng)暗示了它的分量。這絕對不是一道讓你手算幾個小規(guī)模排列數(shù)就能解決的題目它考察的是如何將復雜的組合約束通過一系列經(jīng)典的組合工具轉(zhuǎn)化成一個可以高效計算的數(shù)學模型。我拿到這個題的第一反應是去理解它到底在問什么。通常這類“Yet Another”問題會在經(jīng)典排列問題上增加一些新的、奇怪的限制條件。比如可能要求排列中某些位置必須大于其相鄰位置即“峰”或“谷”或者要求某些數(shù)字對必須滿足特定的大小關(guān)系。這道題的具體描述雖然輸入中未給出但根據(jù)經(jīng)驗和關(guān)鍵詞可以推斷很可能涉及對排列中“逆序?qū)Α?、“上升序列”或某種“模式”出現(xiàn)次數(shù)的限制。問題的核心挑戰(zhàn)在于直接枚舉所有排列并檢查條件在n稍大時比如n1000是完全不可能的我們需要一個能在多項式時間內(nèi)通常是O(n log n)或O(n^2)計算出答案的解析方法或算法。那么標題中給出的工具鏈“容斥 - 生成函數(shù) - 多項式”就是解決此類問題的標準“組合套餐”。容斥原理是我們處理“至少”或“恰好”滿足某些條件計數(shù)的利器它能把復雜的交集條件轉(zhuǎn)化為更簡單的補集運算。生成函數(shù)尤其是普通生成函數(shù)OGF和指數(shù)生成函數(shù)EGF則是將組合對象如排列和計數(shù)序列轉(zhuǎn)化為代數(shù)對象的魔法它允許我們使用代數(shù)運算如乘法、求逆、復合來代替復雜的組合推理。最后多項式則是承載生成函數(shù)的容器問題的答案往往就是某個多項式的某一項系數(shù)而我們需要通過多項式運算如卷積、求逆、exp/ln來高效地計算出這個系數(shù)。接下來我會按照“理解約束 - 容斥轉(zhuǎn)化 - 生成函數(shù)建模 - 多項式求解”這條主線一步步拆解這個問題的通用解法思路并分享在實現(xiàn)過程中容易踩坑的細節(jié)。即使你之前對生成函數(shù)有些發(fā)怵我相信通過這個具體問題的牽引你也能感受到這套組合工具的威力與美感。1.1 從排列約束到容斥框架第一步也是最關(guān)鍵的一步是把題目中那些關(guān)于排列的、難以直接處理的條件轉(zhuǎn)化成一個可以用容斥原理處理的邏輯形式。我們假設(shè)題目要求排列p[1..n]滿足k個限制條件每個條件可能形如“數(shù)字i不能出現(xiàn)在位置j”或者“數(shù)字a必須排在數(shù)字b之前”甚至是更復雜的“不存在長度為3的下降子序列”。直接計算滿足所有條件的排列數(shù)非常困難。容斥原理提供了一個框架滿足所有條件的排列數(shù) 總排列數(shù) - 至少違反一個條件的排列數(shù) 至少違反兩個條件的排列數(shù) - ...。這里“違反條件”通常比“滿足條件”更容易刻畫。例如如果條件是“數(shù)字i不能出現(xiàn)在位置j”那么“違反”這個條件就意味著“數(shù)字i恰好出現(xiàn)在位置j”這實際上固定了一個位置剩下的部分就是一個(n-1)的排列很容易計算。因此我們的策略是定義一組“壞事件”A1, A2, ..., Am每個壞事件對應違反了某個或某組原始條件。利用容斥原理答案 Σ_{S ? [m]} (-1)^{|S|} * (同時違反S中所有壞事件的排列數(shù))。計算“同時違反S中所有壞事件”的排列數(shù)。如果這些壞事件涉及的約束是獨立的比如固定了若干個互不相同的位置那么這個數(shù)就是(n - |S|)!。如果約束間有沖突比如要求同一個位置放兩個不同的數(shù)那么計數(shù)為0。在實際問題中壞事件的設(shè)計需要技巧。有時我們需要對“違反條件”的程度進行更精細的劃分比如不是簡單地“違反”而是“違反至少t次”這可能會引入新的求和指標。這時生成函數(shù)就能很好地幫我們管理這些指標。1.2 生成函數(shù)將組合結(jié)構(gòu)轉(zhuǎn)化為代數(shù)方程當我們用容斥原理寫出一個帶多重求和的表達式后生成函數(shù)就能大顯身手了。它的核心思想是把一個序列a_0, a_1, a_2, ...包裝成一個形式冪級數(shù)A(x) Σ a_i * x^i。這里的x只是一個形式符號它的指數(shù)i通常代表我們關(guān)心的某個組合量如違反條件的次數(shù)、選取的元素個數(shù)等。為什么這樣做有用因為冪級數(shù)的運算規(guī)則加法、乘法、復合恰好對應了組合結(jié)構(gòu)的合并、拼接、選擇等操作。例如乘法如果A(x)計數(shù)“完成任務甲”的方式數(shù)任務甲有i種方式則貢獻a_i * x^iB(x)計數(shù)“完成任務乙”的方式數(shù)那么A(x) * B(x)的系數(shù)就計數(shù)了“先獨立完成甲再獨立完成乙”的所有方式數(shù)并且總“量”是兩者之和。這在組合中稱為卷積。指數(shù)生成函數(shù)EGF專門用于處理帶標號對象的計數(shù)比如排列。排列的EGF是Σ_{n0} n! / n! * x^n Σ x^n 1/(1-x)。但更重要的是當我們用EGF表示一個“結(jié)構(gòu)”時其乘法對應了標號集合的合并與重排這非常適合處理排列問題。在這道題中我們很可能會構(gòu)造一個生成函數(shù)F(x)其中[x^k] F(x)即x^k的系數(shù)代表了與“違反條件”的某種度量相關(guān)的計數(shù)。通過容斥原理最終的答案可以表示為對這個生成函數(shù)進行一系列運算如求1 - F(x)的某種變換后提取x^n系數(shù)或代入x1等操作的結(jié)果。1.3 多項式科技從生成函數(shù)到可計算系數(shù)生成函數(shù)給出了一個優(yōu)美的封閉形式但我們的最終目標是要一個具體的數(shù)字——通常是這個生成函數(shù)某一項的系數(shù)。這時就需要“多項式科技”了。我們通常只能在模一個質(zhì)數(shù)如998244353,1000000007的意義下進行計算因為這些質(zhì)數(shù)域存在原根支持快速數(shù)論變換NTT從而能在O(n log n)時間內(nèi)完成多項式乘法、求逆、exp、ln等操作。整個解題過程可以看作一個多項式計算流水線建立模型根據(jù)容斥原理推導出答案的生成函數(shù)表達式。多項式表示將生成函數(shù)F(x)截斷到n次因為高于n次的項對答案無貢獻用長度為O(n)的多項式系數(shù)數(shù)組來表示它。多項式運算按照表達式對多項式進行一系列運算。常見的操作包括乘法/卷積對應獨立事件的組合。求逆求解1 / (1 - F(x))這類形式。指數(shù)函數(shù)Exp當我們需要計算“將若干個不可區(qū)分的組件組合起來”時EGF的Exp會出現(xiàn)。對數(shù)函數(shù)Ln常與Exp配對出現(xiàn)用于解耦。提取系數(shù)從最終得到的多項式G(x)中取出x^n的系數(shù)或者根據(jù)題意可能是對系數(shù)進行求和即為答案。這個過程將組合推理完全轉(zhuǎn)化為了代數(shù)計算使得我們能夠處理規(guī)模很大的n例如n10^5這是暴力枚舉或動態(tài)規(guī)劃無法企及的。2. 一個具體模型帶禁止位置的排列問題為了讓大家更有體感我們不妨用一個經(jīng)典的、與題目可能相關(guān)的模型來具體演練一下這套流程計算恰好有k個位置滿足p_i i的排列數(shù)即恰好有k個不動點。這個問題被稱為“錯位排列”的推廣。雖然原題可能更復雜但這個例子涵蓋了容斥、生成函數(shù)和多項式的基本運用。2.1 容斥原理推導設(shè)A_i為事件“數(shù)字i放在位置i”即它是一個不動點違反了“錯位”的要求?？偱帕袛?shù)n!。至少有一個不動點的排列數(shù)Σ |A_i| C(n,1)*(n-1)!。至少有兩個不動點的排列數(shù)Σ |A_i ∩ A_j| C(n,2)*(n-2)!其中ij?！辽儆衪個不動點的排列數(shù)C(n, t) * (n-t)!。根據(jù)容斥原理沒有不動點的排列數(shù)即經(jīng)典錯排數(shù)D_n為D_n Σ_{t0}^{n} (-1)^t * C(n, t) * (n-t)! n! * Σ_{t0}^{n} (-1)^t / t!。而我們要求的是恰好有k個不動點的排列數(shù)。這可以理解為先選定k個位置作為不動點有C(n, k)種選法然后剩下的n-k個位置必須形成一個無不動點的排列即錯排。因此答案Ans_k為Ans_k C(n, k) * D_{n-k} C(n, k) * (n-k)! * Σ_{t0}^{n-k} (-1)^t / t!。這個公式已經(jīng)可以計算了。但如果我們想為所有k0..n一次性求出Ans_k或者n很大這個求和式的計算就顯得有些孤立。這時生成函數(shù)可以提供更統(tǒng)一的視角。2.2 生成函數(shù)建模我們嘗試構(gòu)造一個生成函數(shù)使其x^k的系數(shù)與Ans_k相關(guān)。觀察公式Ans_k C(n, k) * (n-k)! * Σ_{t0}^{n-k} (-1)^t / t!。 令a_m m! * Σ_{t0}^{m} (-1)^t / t!那么Ans_k C(n, k) * a_{n-k}。我們知道數(shù)列C(n, k)的生成函數(shù)是(1x)^n。而數(shù)列a_m的指數(shù)生成函數(shù)EGFA(x)是什么a_m m! * [x^m] ( Σ_{t0} (-1)^t / t! * x^t )不對因為求和上限是m不是無窮。這提示我們a_m其實是m!與錯排數(shù)D_m的卷積讓我們重新審視。實際上D_m m! * Σ_{t0}^{m} (-1)^t / t!。所以a_m D_m。 那么Ans_k C(n, k) * D_{n-k}?，F(xiàn)在考慮二元生成函數(shù)F(x, y)我們希望[x^n y^k] F(x, y)正比于Ans_k。這不容易直接構(gòu)造。更常見的做法是固定n為序列{Ans_k}構(gòu)造一個普通生成函數(shù)OGF。對于固定的n定義G_n(z) Σ_{k0}^{n} Ans_k * z^k。 將Ans_k C(n, k) * D_{n-k}代入G_n(z) Σ_{k0}^{n} C(n, k) * D_{n-k} * z^k Σ_{j0}^{n} C(n, n-j) * D_j * z^{n-j}令j n-k Σ_{j0}^{n} C(n, j) * D_j * z^{n-j}。這個形式還不夠漂亮。我們利用D_j的EGF。已知錯排數(shù)的EGF是D(x) Σ_{j0} D_j / j! * x^j e^{-x} / (1-x)。 那么G_n(z)可以寫成G_n(z) z^n * Σ_{j0}^{n} C(n, j) * (D_j / j!) * (j!) * z^{-j} 這樣處理起來很麻煩。一個更聰明的辦法是回到容斥的源頭。定義生成函數(shù)H(t)其中[t^s] H(t)表示至少有s個不動點的排列數(shù)。根據(jù)容斥我們知道H(t) Σ_{s0}^{n} (至少s個不動點的排列數(shù)) * t^s。 而“至少s個不動點”的排列數(shù)等于先選s個位置作為不動點C(n, s)然后剩下n-s個位置任意排列(n-s)!。所以H(t) Σ_{s0}^{n} C(n, s) * (n-s)! * t^s Σ_{s0}^{n} n! / s! * t^s。那么恰好有k個不動點的排列數(shù)就是[t^k] H(t-1)。這是因為容斥原理在生成函數(shù)中的體現(xiàn)就是代入-1進行“符號交替”。我們可以驗證H(t-1) Σ_{s0}^{n} n! / s! * (t-1)^s Σ_{s0}^{n} n! / s! * Σ_{k0}^{s} C(s, k) * t^k * (-1)^{s-k}交換求和順序[t^k] H(t-1) Σ_{sk}^{n} n! / s! * C(s, k) * (-1)^{s-k} n! / k! * Σ_{sk}^{n} (-1)^{s-k} / (s-k)! n! / k! * Σ_{t0}^{n-k} (-1)^t / t! C(n, k) * (n-k)! * Σ_{t0}^{n-k} (-1)^t / t! Ans_k。完美所以我們得到了一個簡潔的生成函數(shù)表達式Ans_k [t^k] Σ_{s0}^{n} n! / s! * (t-1)^s。2.3 多項式計算實現(xiàn)現(xiàn)在我們要計算G(t) Σ_{s0}^{n} n! / s! * (t-1)^s這個多項式然后取出它的各個系數(shù)。這完全是一個多項式運算問題。構(gòu)造多項式令F(x) Σ_{s0}^{n} (n! / s!) * x^s。這是一個簡單的多項式系數(shù)a_s n! / s!。多項式平移我們需要計算G(t) F(t-1)。這等價于計算F(x)在x t-1處的值。多項式平移可以通過卷積來實現(xiàn)。設(shè)F(x) Σ a_i x^i則F(xc) Σ a_i (xc)^i Σ a_i Σ_{j0}^{i} C(i,j) c^{i-j} x^j。交換求和順序后這可以寫成兩個序列的卷積b_j a_j * j!和c_{i-j} c^{i-j} / (i-j)!的卷積結(jié)果再除以j!。這就是經(jīng)典的多項式“泰勒平移”算法利用卷積和階乘預處理可以在O(n log n)時間內(nèi)完成。提取系數(shù)平移后得到的多項式G(t)的系數(shù)[t^k] G(t)就是我們要求的Ans_k。在實際代碼實現(xiàn)中以模998244353為例步驟如下#include bits/stdc.h using namespace std; const int mod 998244353, G 3; // NTT模數(shù)與原根 // 此處省略NTT多項式乘法、求逆等模板代碼... vectorint solve_fixed_point(int n) { // 1. 預處理階乘和逆元 vectorint fac(n1), ifac(n1); fac[0] 1; for(int i1; in; i) fac[i] 1LL * fac[i-1] * i % mod; ifac[n] powmod(fac[n], mod-2); for(int in; i1; i--) ifac[i-1] 1LL * ifac[i] * i % mod; // 2. 構(gòu)造多項式 F(x) Σ_{s0..n} (n! / s!) * x^s vectorint F(n1); for(int s0; sn; s) { F[s] 1LL * fac[n] * ifac[s] % mod; // n! / s! } // 3. 計算 G(t) F(t-1)使用多項式平移算法 // 多項式平移已知 F(x) Σ a_i x^i, 求 F(xc) 的各項系數(shù) // 算法令 A[i] a_i * i! , B[j] c^j / j! // 計算 C A * B (卷積), 則 F(xc) 的系數(shù) coeff_k C[k] / k! int c mod - 1; // c -1 vectorint A(n1), B(2*n1); for(int i0; in; i) A[i] 1LL * F[i] * fac[i] % mod; int pow_c 1; for(int j0; j2*n; j) { B[j] 1LL * pow_c * ifac[j] % mod; pow_c 1LL * pow_c * c % mod; } vectorint C multiply(A, B); // 多項式乘法使用NTT長度需處理 vectorint G(n1); for(int k0; kn; k) { G[k] 1LL * C[k] * ifac[k] % mod; } // G[k] 現(xiàn)在就是恰好有k個不動點的排列數(shù) Ans_k return G; }注意這里的多項式平移算法是標準做法但需要注意卷積后數(shù)組的長度只取前n1項。multiply函數(shù)是封裝好的NTT卷積。通過這個例子我們看到了如何將一個具體的排列計數(shù)問題恰好k個不動點通過容斥原理轉(zhuǎn)化為生成函數(shù)表達式最終落地為多項式平移的計算。原題“LOJ3395”的約束條件肯定比“不動點”更復雜可能涉及逆序?qū)Α⑸仙蛄械鹊浜诵姆椒ㄕ撌窍嗤ǖ亩x合適的“壞事件”應用容斥用生成函數(shù)整合容斥系數(shù)最后用多項式科技快速計算。3. 擴展到更一般的排列約束問題現(xiàn)在讓我們把思路從具體的“不動點”問題抽離回到“Yet Another Permutation Problem”可能涵蓋的更一般情形。常見的排列約束包括局部大小關(guān)系例如要求對于所有i有p_i p_{i1}上升或p_i p_{i1}下降在某些特定位置成立。模式避免要求排列中不出現(xiàn)特定的模式如3,1,2這種子序列?；谥档臈l件例如p_i必須是i的倍數(shù)或者|p_i - i|在一定范圍內(nèi)。對于這類問題一個強大的工具是多項式插值或動態(tài)規(guī)劃與生成函數(shù)的結(jié)合。思路是先設(shè)計一個關(guān)于某個參數(shù)k的動態(tài)規(guī)劃DP求出當參數(shù)為k時的答案f(k)。如果我們可以證明f(k)是一個關(guān)于k的、次數(shù)不超過n的多項式那么我們就可以通過計算f(0), f(1), ..., f(n)這n1個點值然后利用多項式插值拉格朗日插值求出f(k)的多項式表達式進而可以快速求出任意k對應的值。3.1 動態(tài)規(guī)劃設(shè)計與多項式證明如何設(shè)計這樣的DP考慮一個經(jīng)典的例子計算有多少個n的排列其最長上升子序列LIS長度恰好為k。直接計算是困難的。但我們可以計算有多少個排列其LIS長度不超過k。記這個數(shù)為g(k)。那么答案就是g(k) - g(k-1)。如何計算g(k)這需要用到Robinson-Schensted correspondenceRSK對應它建立了排列與楊表Young Tableau之間的一一對應。而一個排列的LIS長度等于其對應的楊表的第一行的長度。標準楊表的形狀是一個整數(shù)分拆λ ? n且第一行長度不超過k的楊表數(shù)量可以由鉤子公式Hook-length Formula給出。對所有滿足λ_1 k的分拆求和可以得到g(k)?？梢宰C明g(k)是關(guān)于k的多項式函數(shù)在k n時是常數(shù)n!。另一個常見的DP狀態(tài)設(shè)計是按值域從小到大插入數(shù)字。設(shè)dp[i][j]表示考慮了1..i這些數(shù)字構(gòu)成的排列實際上是{1..i}的一個排列滿足某種約束的狀態(tài)為j時的方案數(shù)。當插入下一個數(shù)字i1時我們考慮它可以插入的位置并分析狀態(tài)j如何轉(zhuǎn)移。如果狀態(tài)j的定義是“當前有多少個違反條件的位置”或者“當前已經(jīng)形成的某種模式的數(shù)量”那么最終我們關(guān)心的f(k) Σ_{j} dp[n][j]其中求和可能只針對特定的j如jk也可能需要容斥求和。證明f(k)是k的多項式通常需要分析DP轉(zhuǎn)移方程。如果轉(zhuǎn)移方程中只包含k的加減、乘法而不包含除法在模意義下除法可能對應乘法逆元但多項式性可能被破壞并且循環(huán)次數(shù)固定那么f(k)很可能是一個多項式。一個實用的判斷是如果我們可以將DP過程看作是在一個固定大小的圖上進行固定步數(shù)的游走每條邊的權(quán)重是k的多項式那么最終的結(jié)果就是k的多項式。3.2 多項式插值計算一旦我們確定f(k)是次數(shù)不超過D的多項式通常D O(n)并且我們有能力在O(D)或O(D log D)時間內(nèi)計算出f(0), f(1), ..., f(D)這D1個點值那么我們就可以通過插值得到這個多項式。拉格朗日插值公式f(x) Σ_{i0}^{D} f(i) * Π_{j≠i} (x - j) / (i - j)。直接計算的復雜度是O(D^2)。但我們可以優(yōu)化到O(D log D)預處理所有(x - j)的乘積P(x) Π_{j0}^{D} (x - j)。對于每個i計算P(i) Π_{j≠i} (i - j)。這可以通過預處理階乘得到P(i) (i)! * (-1)^{D-i} * (D-i)!。那么f(x) P(x) * Σ_{i0}^{D} f(i) / ( (x-i) * P(i) )。如果我們只需要求一個點值x K那么用這個公式計算是O(D)的。如果我們需要恢復整個多項式系數(shù)就需要用到多項式多點求值、快速插值等更高級的算法復雜度O(D log^2 D)。在實際解題如LOJ3395時我們可能不需要顯式求出整個多項式而是直接利用插值公式計算題目所要求的特定k對應的f(k)。3.3 綜合應用一道模擬賽題的思路假設(shè)有這樣一道題求n的排列中滿足“不存在長度大于等于k的連續(xù)下降子串”的排列數(shù)量。例如對于n4, k3排列[3,2,1,4]是無效的因為它有連續(xù)下降子串[3,2,1]長度為3。我們可以這樣思考容斥用總排列數(shù)n!減去存在至少一個長度k的連續(xù)下降子串的排列數(shù)。但“至少一個”不好直接算因為子串可能重疊。轉(zhuǎn)化考慮排列的“下降塊”劃分。將一個排列劃分成若干個極長的連續(xù)下降子串。例如[4,3,1,2,5]可以劃分成[4,3,1]和[2,5]。要求每個下降塊的長度都 k。生成函數(shù)一個長度為L的下降塊其內(nèi)部只有一種排列方式嚴格遞減。但是這些塊在排列中是有順序的并且塊與塊之間前一個塊的最后一個元素與后一個塊的第一個元素構(gòu)成一個上升關(guān)系。這有點像將n個元素劃分成一些有序的“盒子”每個盒子大小k盒子內(nèi)部強制遞減。DP與多項式設(shè)dp[i]表示i個元素組成若干下降塊每個塊長度k的方案數(shù)。轉(zhuǎn)移時枚舉最后一個塊的長度j (1jk)則dp[i] dp[i-j]因為最后一個塊確定后前面的i-j個元素任意排。初始dp[0]1。我們要求的是dp[n]。但注意這dp[n]計算的是“將n個元素分成若干下降塊”的方案數(shù)每個方案對應一個唯一的排列嗎是的因為塊內(nèi)遞減順序固定塊間順序就是這些塊在排列中的出現(xiàn)順序。但這里我們忽略了塊間元素的相對大小實際上當我們用1..i的數(shù)字時dp[i]計數(shù)的是滿足塊結(jié)構(gòu)的所有排列數(shù)?？梢宰C明這個DP是正確的。生成函數(shù)優(yōu)化這個DP的生成函數(shù)D(x) Σ dp[i] x^i滿足D(x) 1 (x x^2 ... x^{k-1}) * D(x)。所以D(x) 1 / (1 - (x x^2 ... x^{k-1}))。那么dp[n] [x^n] 1/(1 - (xx^2...x^{k-1}))。這個系數(shù)可以用多項式求逆在O(n log n)時間內(nèi)得到。你看通過將問題重新解釋為“下降塊劃分”我們繞開了復雜的容斥直接得到了一個簡潔的生成函數(shù)。這展示了組合視角轉(zhuǎn)化的重要性。原題LOJ3395很可能也需要類似的、更巧妙的組合解釋。4. 實戰(zhàn)中的常見陷阱與優(yōu)化技巧即使思路正確在實現(xiàn)這類涉及容斥、生成函數(shù)和多項式的問題時也有很多細節(jié)容易出錯。下面分享一些我踩過坑后總結(jié)的經(jīng)驗。4.1 容斥系數(shù)與符號處理這是最容易出錯的地方之一。容斥原理的符號是(-1)^{|S|}其中|S|是違反條件的集合大小。但在生成函數(shù)中我們可能會將違反條件的“次數(shù)”作為指數(shù)。例如在“不動點”問題中我們構(gòu)造了H(t) Σ_{s} (至少s個不動點的方案數(shù)) * t^s然后通過H(t-1)得到“恰好”的計數(shù)。這里(t-1)^s展開后t^k項的系數(shù)天然就包含了C(s, k) * (-1)^{s-k}這個容斥系數(shù)。關(guān)鍵檢查點當你的生成函數(shù)代表“至少”或“欽定”某種情況時代入-1或更一般的使用(1-z)的冪往往能實現(xiàn)“恰好”的轉(zhuǎn)換。務必用小數(shù)據(jù) (n1,2,3) 手動驗證你的生成函數(shù)表達式。計算幾個系數(shù)看看是否符合暴力枚舉的結(jié)果。4.2 多項式運算的邊界與長度進行多項式乘法、求逆、exp/ln時必須明確你需要保留的次數(shù)。例如在計算[x^n] 1/(1 - A(x))時如果A(x)的次數(shù)是m那么1/(1-A(x))的x^n項系數(shù)可能依賴于A(x)的更高次項嗎不會因為這是一個無限級數(shù)但在模x^{n1}的意義下計算就足夠了。所以我們通常在模x^{M}的意義下進行多項式運算其中M是所需的最大次數(shù)加一。常見錯誤多項式乘法后結(jié)果數(shù)組長度應該是len(A)len(B)-1但如果你只關(guān)心前n項可以只保留前n1項以節(jié)省計算量和內(nèi)存。多項式求逆、exp、ln等操作要求初始多項式的常數(shù)項滿足特定條件如求逆要求常數(shù)項非零exp要求常數(shù)項為0。在執(zhí)行這些操作前務必檢查。4.3 模運算下的除法與階乘組合計數(shù)通常涉及大量的階乘n!和組合數(shù)C(n, k)。在模質(zhì)數(shù)P下我們需要預處理階乘fac[i]和階乘的逆元ifac[i]。這樣C(n, k) fac[n] * ifac[k] % P * ifac[n-k] % P。注意事項預處理數(shù)組的長度至少要開到n的最大可能值通常還會多開一點如n5以防越界。當公式中出現(xiàn)除法時如1/s!在模運算下必須乘以s!的乘法逆元。永遠不要直接做除法。4.4 時間復雜度的分析與優(yōu)化這類問題的典型時間復雜度是O(n log n)或O(n log^2 n)取決于多項式運算的復雜度。NTT的卷積是O(n log n)。多項式求逆、exp、ln可以通過牛頓迭代法在O(n log n)內(nèi)完成。優(yōu)化點減少多項式運算次數(shù)有時表達式可以化簡。例如exp(A(x)) * exp(B(x)) exp(A(x)B(x))先做加法再做一次exp比做兩次exp再卷積要快。利用對稱性如果生成函數(shù)是偶數(shù)函數(shù)或奇數(shù)函數(shù)可能可以簡化計算。分治NTT如果DP轉(zhuǎn)移是dp[i] Σ_{j i} dp[j] * a[i-j]這種形式且a已知那么這就是一個標準的卷積可以用NTT一次算出。如果轉(zhuǎn)移方程更復雜可能需要分治NTT將復雜度從O(n^2)降為O(n log^2 n)。4.5 調(diào)試與對拍這類題目調(diào)試起來比較困難因為中間結(jié)果多項式系數(shù)往往很長。我的調(diào)試策略是小數(shù)據(jù)暴力寫一個O(n! * n)的暴力程序枚舉所有排列并檢查條件計算n8時的答案。用這個來驗證你的多項式程序在小數(shù)據(jù)下的結(jié)果。中間輸出將關(guān)鍵步驟的多項式前幾項系數(shù)打印出來與手算或另一種思路的計算結(jié)果對比。例如計算“至少s個不動點”的生成函數(shù)H(t)你可以手動計算n4時H(t)的系數(shù)與程序輸出對比。對拍如果題目有部分分比如n20用暴力程序跑部分分用多項式程序跑全部數(shù)據(jù)在交叉部分n20驗證答案是否一致。靜態(tài)查錯仔細檢查容斥的符號、生成函數(shù)中變量的意義是指數(shù)還是普通系數(shù)、多項式運算的長度、模運算的正確性。處理這類問題就像在搭建一個精密的儀器。容斥原理是設(shè)計圖生成函數(shù)是傳動系統(tǒng)多項式算法是加工工具。任何一個環(huán)節(jié)的微小誤差都可能導致最終結(jié)果謬以千里。但一旦你成功搭建起來看到對于n100000的規(guī)模也能在秒級內(nèi)計算出答案那種成就感是無與倫比的。它讓你真正體會到組合數(shù)學不僅僅是巧妙的計數(shù)更是可以將復雜問題轉(zhuǎn)化為可計算模型的強大數(shù)學框架。