1. 項目概述從一道組合數學題說起最近在刷題平臺daimayuan上遇到了一個名為“Good Permutations”的每日一題。題目本身屬于組合數學的范疇但它的魅力在于它不像那些一眼就能看出套路的動態規劃或者數據結構題而是需要你靜下心來仔細分析排列的內在結構并找到一種高效的計算方法。很多朋友第一次看到這個題可能會有點懵不知道從何下手或者暴力枚舉后發現數據范圍根本不允許。這正是我想寫這篇分享的原因——我想把我解決這道題以及類似“好排列”問題的完整思考路徑、核心的數學推導以及最終如何轉化為高效代碼的整個過程詳細地記錄下來。簡單來說“Good Permutations”問題探討的是在一個特定規則下有多少個長度為n的排列是“好”的。這里的“好”通常與排列中元素之間的某種相對位置關系有關比如要求對于所有i某個與i相關的值比如i的某個函數在排列中的位置滿足特定條件。這類問題在算法競賽和面試中并不少見它考察的是選手將實際問題抽象為數學模型并利用組合數學知識進行化簡和計算的能力。如果你對排列組合、容斥原理或者遞推關系感興趣或者正在準備需要考察數學思維的編程面試那么這篇內容會非常適合你。我會從最樸素的想法開始一步步引導你看到問題的本質并最終給出一個清晰、可復現的解決方案。2. 問題定義與核心思路拆解2.1 原題回顧與形式化定義首先我們需要明確“Good Permutations”的具體定義。由于daimayuan的題目可能會隨時間變化我在這里基于常見的“好排列”問題類型給出一個具有代表性的形式化描述這能覆蓋絕大部分此類問題的核心。假設我們有一個長度為n的排列p[1], p[2], ..., p[n]它是1到n這些整數的一個重新排列。我們稱這個排列是“好”的如果它滿足以下條件對于每一個位置i(1 i n)排列在位置i上的值p[i]與某個和i相關的“目標值”之間的關系符合特定規則。一個非常經典且能引申出深刻數學內涵的規則是對于每個i要求p[i]不能等于i。這就是著名的“錯位排列”Derangement問題。但題目“Good Permutations”往往會有更復雜或更一般化的約束。例如約束可能形如p[i]不能等于f(i)其中f是一個給定的函數?；蛘呒s束可能涉及多個位置之間的關系比如p[i]和p[i1]的奇偶性需要不同。為了進行一般性的討論我們假設“好”的定義為對于所有i排列p滿足一組形如p[i] ! g(i)的條件這里的g(i)是一個從位置索引i映射到值域{1, 2, ..., n}的函數。我們的目標是計算長度為n的、滿足所有n個約束條件的排列總數。注意實際問題可能比這更復雜可能包含“必須等于”或者更復雜的邏輯關系。但p[i] ! g(i)這種“禁止”型約束是最常見的基礎很多復雜問題可以通過轉化或容斥原理歸結為此類問題。2.2 解題的核心思路從暴力到精妙數學面對這樣的計數問題一個最直接的想法是暴力生成所有n!個排列然后逐一檢查是否滿足所有條件。當n很小比如n 10時這是可行的。但題目給定的n往往很大比如n 10^5甚至更大n!是一個天文數字暴力法完全不可行。這就迫使我們尋找數學上的規律將問題化簡。解決這類問題的核心思路通常遵循以下路徑識別問題本質首先判斷這是否是一個經典的排列計數問題如錯位排列、受限排列等。嘗試將題目描述轉化為清晰的數學模型。嘗試動態規劃DP對于序列計數問題DP是常用工具。我們可能定義dp[i][state]表示處理到前i個位置處于某種狀態state下的方案數。但state的設計是關鍵它需要能概括之前的選擇對后續決策的影響。對于涉及全局匹配的排列問題狀態可能非常復雜導致DP不可行?？紤]容斥原理當問題要求“所有條件都必須滿足”時計算其補集至少有一個條件不滿足有時會更簡單。容斥原理正是處理“至少一個”這類問題的利器。公式如下|A1 ∩ A2 ∩ ... ∩ An| |S| - Σ|Ai| Σ|Ai ∩ Aj| - Σ|Ai ∩ Aj ∩ Ak| ... (-1)^n |A1 ∩ A2 ∩ ... ∩ An|其中S是所有排列的集合大小為n!Ai表示第i個條件被違反即p[i] g(i)的排列集合。計算交集|Ai ∩ Aj ∩ ...|的大小意味著我們固定了若干位置p[i] g(i), p[j] g(j), ...然后計算剩下位置自由排列的方案數。這比直接計算原問題看起來更可行。尋找更優的數學模型或結論對于某些特殊的函數g(i)可能存在封閉公式或簡單的遞推關系。例如經典的錯位排列D(n)即g(i)i就有公式D(n) n! * Σ_{k0}^{n} (-1)^k / k!以及遞推式D(n) (n-1) * [D(n-1) D(n-2)]。轉化為圖論問題雙射排列問題有時可以轉化為二分圖上的匹配問題。將位置i和值j看作二分圖的兩部分節點如果j ! g(i)則在i和j之間連一條邊。那么“好排列”就對應這個二分圖的一個完美匹配。計算完美匹配的數量在某些特殊圖如行列式可算的圖上有高效算法但一般圖是 #P-難問題。對于“Good Permutations”經過分析容斥原理往往是突破口。因為它將“所有條件都不違反”這個難以直接計算的問題轉化為了計算一系列“固定某些位置違反條件”的子問題而這些子問題的規模更小且可能具有規律性。3. 核心細節解析容斥原理的應用與化簡3.1 應用容斥原理的一般形式讓我們將容斥原理應用到我們的問題中。定義S: 所有n!個排列的集合。Ai: 滿足p[i] g(i)的排列集合即違反第i條約束。我們要求的是所有約束都滿足的排列數即|A1^c ∩ A2^c ∩ ... ∩ An^c|其中^c表示補集。根據德摩根定律和容斥原理|A1^c ∩ A2^c ∩ ... ∩ An^c| |S| - |A1 ∪ A2 ∪ ... ∪ An| Σ_{k0}^{n} (-1)^k * (所有大小為k的Ai交集之和)更具體地令F(k)表示至少固定k個位置滿足p[i] g(i)即違反這k個約束的排列數之和。注意這里“至少固定k個”意味著我們選定了某k個具體的約束讓其違反然后對這k個位置強制p[i] g(i)剩下的n-k個位置可以任意排列但可能偶然滿足或違反其他約束。那么根據容斥原理答案 Σ_{k0}^{n} (-1)^k * F(k)其中F(k) Σ_{1 i1 i2 ... ik n} |Ai1 ∩ Ai2 ∩ ... ∩ Aik|。 而|Ai1 ∩ Ai2 ∩ ... ∩ Aik|表示我們固定了k個位置i1, i2, ..., ik使得p[i1]g(i1), p[i2]g(i2), ..., p[ik]g(ik)。那么剩下的n-k個位置可以任意排列方案數是(n-k)!。所以F(k) (n-k)! * (滿足條件的k元組 (i1, i2, ..., ik) 的數量)。 這里的“滿足條件”指的是我們選出的這k個索引i1, i2, ..., ik它們對應的值g(i1), g(i2), ..., g(ik)必須兩兩不同。因為如果g(ia) g(ib)且ia ! ib那么我們就要求p[ia]和p[ib]都等于同一個值這在排列中是不可能的一個值不能出現在兩個位置。因此這樣的k元組是無效的不應計入F(k)。3.2 關鍵轉化計算有效k元組的數量于是問題的核心從計算排列數轉化為了計算從{1,2,...,n}中選出k個索引的方案數使得這些索引對應的g(i)值兩兩不同。這引導我們從一個新的視角看問題?？紤]一個二分圖左邊是n個位置節點L{1,2,...,n}右邊是n個值節點R{1,2,...,n}。我們從位置i向值g(i)連一條“禁止邊”因為p[i]不能等于g(i)。但在容斥原理的語境下當我們固定p[i]g(i)時我們實際上是使用了這條邊。所以選取一個有效的k元組{i1,...,ik}等價于在二分圖中選取一個大小為k的匹配其中每條匹配邊連接(i, g(i))。并且這個匹配必須是“左完美”于這k個點的即這k條邊沒有共享任何左右節點。因此F(k) (n-k)! * M(k)其中M(k)表示從這n條特定的邊(i, g(i))中選出k條邊構成一個匹配即無沖突的方案數。3.3 針對特定 g(i) 的進一步化簡M(k)的計算依賴于函數g的具體形式。我們分析幾種常見情況情況一經典錯位排列即 g(i) i。此時邊集就是{(1,1), (2,2), ..., (n,n)}。這n條邊共享了所有節點每個左節點i只連向右節點i每個右節點i也只被左節點i連接。因此要從中選出k條邊構成一個匹配意味著我們選擇的k條邊必須連接k對不同的左右節點。這等價于從n個節點對中選出k對。所以M(k) C(n, k)組合數。 于是F(k) C(n, k) * (n-k)! n! / k!。 代入容斥公式答案 Σ_{k0}^{n} (-1)^k * n! / k! n! * Σ_{k0}^{n} (-1)^k / k!這就是錯位排列的經典公式。情況二g(i) 是一個置換即 g 是 {1,...,n} 到自身的一個雙射。此時邊集(i, g(i))構成了一個完美匹配。要從中選出k條邊構成一個匹配這k條邊自然就是原匹配的一個子集且它們之間不可能沖突因為原匹配的邊之間就沒有公共節點。所以選出任意k條邊都是一個有效的匹配。因此M(k) C(n, k)。 結果和情況一相同答案 n! * Σ_{k0}^{n} (-1)^k / k!。這意味著當禁止條件構成一個置換時“好排列”的數量等于錯位排列數。這是一個很有趣的結論。情況三g(i) 具有更一般的結構。例如g(i) (i1) mod n循環移位或者g(i) n1-i反轉。此時邊集(i, g(i))可能形成多個環或鏈的結構。計算M(k)就變成了在一個特定的圖由這些邊構成中選取k條互不相鄰的邊的方案數。這是一個圖論中的“匹配計數”問題。對于由多個不相交的環或鏈構成的圖匹配數可以通過動態規劃在單個環/鏈上計算然后利用乘法原理組合起來。以g(i) (i1) mod n循環移位為例它形成了一個大環1-2-3-...-n-1。我們需要計算在這個n個節點的環上選取k條互不相鄰的邊的方案數。這是一個經典問題其方案數為C(n-k, k) C(n-k-1, k-1)具體推導涉及組合數學中的“隔板法”或遞推。那么M(k)就等于這個數。然后F(k) M(k) * (n-k)!再代入容斥公式求和。3.4 計算策略總結通過以上分析我們將“Good Permutations”的計數流程總結如下建模根據題目定義確定禁止函數g(i)。構圖根據g(i)構建邊集E {(i, g(i)) | 1in}。分析這個邊集構成的圖的結構通常是若干個連通分量每個分量是鏈或環。計算 M(k)對于每個連通分量鏈或環計算在該分量上選取t條匹配邊的方案數dp_c[t]。然后使用DP或生成函數卷積將所有分量的方案數合并得到整體的M(k)對于所有k0..n。對于鏈和環有標準的DP遞推式鏈長度為m設f_chain[m][t]為在長度為m的鏈上選t條不相鄰邊的方案數。有f_chain[m][t] C(m-t1, t)也可以用DP計算f_chain[m][t] f_chain[m-1][t] f_chain[m-2][t-1]邊界條件f_chain[0][0]1。環長度為m設f_cycle[m][t]為在長度為m的環上選t條不相鄰邊的方案數。有公式f_cycle[m][t] C(m-t, t) C(m-t-1, t-1) (m/(m-t)) * C(m-t, t)(對于m1)。也可以用DP通過討論是否選擇第一條邊來推導。應用容斥得到M(k)后計算F(k) M(k) * (n-k)!。注意階乘(n-k)!和M(k)都可能很大通常需要在模意義下計算如模1e97。求和計算最終答案Ans Σ_{k0}^{n} (-1)^k * F(k) mod MOD。4. 實操過程以循環移位為例的完整實現為了讓大家更清楚地理解整個流程我們以一個具體的、也是常見的變種為例計算滿足p[i] ! (i mod n) 1的排列數。也就是說對于位置i禁止它放置的數字是i1當in時禁止放置1。這就是一個循環移位的禁止規則。4.1 步驟一問題分析與建模題目求長度為n的排列p的數量使得對于所有1 i n都有p[i] ! i % n 1。當1 i n-1時條件為p[i] ! i1。當i n時條件為p[n] ! 1。因此禁止函數g(i)定義為g(i) i1, for 1 i n-1g(n) 14.2 步驟二構圖與結構分析邊集E {(1,2), (2,3), (3,4), ..., (n-1, n), (n, 1)}。 這n條邊恰好連接成一個長度為n的環。左節點和右節點都是{1,2,...,n}但這個圖的結構是一個單一的環。我們需要計算在這個n個節點的環上選取k條互不相鄰的邊的方案數M(k)。如前所述對于環有公式M(k) f_cycle(n, k) C(n-k, k) C(n-k-1, k-1)其中規定C(a, b)0當b0或ba。 這個公式可以這樣理解將環剪開一條邊變成鏈方案數為C(n-k, k)鏈的公式。但這樣會漏掉同時包含被剪開的那條邊及其相鄰邊的情況實際上這個公式有組合解釋也可以從遞推推導出來。我們更傾向于使用遞推DP來求f_cycle[m][t]因為它更通用且易于在模意義下編程實現。環的DP遞推 考慮一個長度為m的環。我們考慮第一條邊(1,2)在圖中對應(1, g(1))。情況A不選第一條邊。那么剩下的部分是一個長度為m-1的鏈節點2,3,...,m,1按順序連接但首尾未連接。在長度為m-1的鏈上選k條邊的方案數是f_chain(m-1, k)。情況B選第一條邊。那么第二條邊(2,3)和最后一條邊(m,1)都不能選了因為與第一條邊相鄰。因此我們需要從剩下的部分一個長度為m-3的鏈節點4,5,...,m中選取k-1條邊。方案數是f_chain(m-3, k-1)。因此f_cycle(m, k) f_chain(m-1, k) f_chain(m-3, k-1)。 其中f_chain(m, t)是鏈上選不相鄰邊的方案數有f_chain(m, t) C(m-t1, t)也可以用DPf_chain(m, t) f_chain(m-1, t) f_chain(m-2, t-1)。在我們的問題中m n。所以M(k) f_cycle(n, k)。4.3 步驟三預計算與DP實現我們需要計算所有k從0到n的M(k)以及階乘fact[i]和階乘逆元invfact[i]用于計算組合數。假設模數為MOD 1e97。MOD 10**97 def solve_good_permutations_cycle_shift(n): # 1. 預計算階乘和階乘逆元用于組合數計算 fact [1] * (n1) inv_fact [1] * (n1) for i in range(1, n1): 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 def C(a, b): if b 0 or b a: return 0 return fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD # 2. 計算鏈的匹配數 f_chain(m, t) C(m-t1, t) # 或者用DP表這里我們用公式 def f_chain(m, t): if t 0 or t (m1)//2: return 0 return C(m - t 1, t) # 3. 計算環的匹配數 f_cycle(m, t) def f_cycle(m, t): if t 0 or t m//2: return 0 if m 0: return 1 if t 0 else 0 if m 1: return 1 if t 0 else 0 # 環長為1一條邊不能選選了自環這里我們的邊是(i,g(i))當n1時g(1)2?不n1時g(1)1 mod 11? 需要單獨處理n1) # 遞推式: f_cycle(m, t) f_chain(m-1, t) f_chain(m-3, t-1) res f_chain(m-1, t) if t 1 and m 3: res (res f_chain(m-3, t-1)) % MOD return res # 4. 計算 M(k) f_cycle(n, k) M [0] * (n1) for k in range(0, n1): M[k] f_cycle(n, k) # 5. 應用容斥原理求和 ans 0 for k in range(0, n1): Fk M[k] * fact[n - k] % MOD # F(k) M(k) * (n-k)! sign -1 if k % 2 else 1 ans (ans sign * Fk) % MOD return ans % MOD # 測試 n1,2,3,4 for n in range(1, 6): print(fn{n}: {solve_good_permutations_cycle_shift(n)})注意當n1時我們的禁止條件是p[1] ! 2但值域只有{1}所以沒有滿足條件的排列答案應為0。上述代碼中f_cycle(1,0)1,f_cycle(1,1)0M[0]1,M[1]0。F(0)1*1!1,F(1)0*0!0。答案1 - 0 1這顯然不對。問題出在n1時我們的圖模型不成立因為g(1)2超出了值域。實際上對于n1條件p[1]!2是恒成立的因為p[1]只能是1所以應該有一個排列。但原題通常n1且g(i)在值域內。這里為了演示我們假設n2。在實際解題時必須單獨處理邊界情況。對于循環移位g(i)i%n1當n1時g(1)1%111這會產生歧義。通常題目會保證n2或者明確定義。我們修正一下對于n2上述算法正確。n1時排列[1]滿足p[1]!2恒真所以答案是1。但我們的g(1)應該是無效的。所以在實現時對于n1直接返回1如果題目邏輯是恒真或根據具體定義處理。4.4 步驟四復雜度分析與優化上述算法的時間復雜度為O(n^2)因為我們需要計算M(k)對于所有k而每個f_cycle(n,k)的計算是O(1)的如果預計算了組合數。主要的循環是k從0到n所以是O(n)。但是如果我們使用DP來計算f_chain和f_cycle的表而不是用組合數公式也可以達到O(n^2)。對于n高達10^5的情況O(n^2)是不可接受的。我們需要優化。觀察發現M(k)只在k n/2時非零因為環上最多選floor(n/2)條不相鄰的邊。更重要的是對于環的匹配數存在一個生成函數或者我們可以利用其與組合數的關系通過一次卷積或多項式運算來得到所有M(k)。實際上有結論f_cycle(n, k)的生成函數與 Chebyshev 多項式有關。但對于編程競賽我們通常不需要處理極大的n或者題目設計的n在2000左右O(n^2)的DP是可以接受的。如果n真的很大比如10^5并且模數是 NTT 友好的如998244353我們可以使用生成函數和 NTT 卷積在O(n log n)內計算出所有M(k)。具體來說單個環的匹配數生成函數是G(x) Σ_{k} f_cycle(n, k) * x^k。對于多個不相交的環/鏈總生成函數是它們各自生成函數的卷積。得到M(k)后再與(n-k)!進行卷積實際上是點乘最后容斥求和。這屬于更高級的范疇在此不展開。對于大多數面試或競賽題n在1000量級O(n^2)的DP是完全可行的。上述代碼清晰展示了從問題到數學模型再到代碼實現的完整邏輯鏈。5. 常見問題與排查技巧實錄在實際實現和解決這類問題時我踩過不少坑也總結了一些技巧。5.1 容斥原理符號處理最容易出錯的地方是容斥原理的正負號。公式是Σ (-1)^k * F(k)。在代碼中我通常這樣寫ans 0 for k in range(0, n1): sign 1 if k % 2 0 else -1 # 或者 sign (-1)**k term sign * F(k) % MOD ans (ans term) % MOD確保最后對MOD取模后得到正數ans (ans MOD) % MOD。5.2 組合數計算的邊界條件計算組合數C(a, b)時必須處理b 0或b a的情況返回0。在預計算階乘逆元時要確保fact[0] inv_fact[0] 1。對于較大的n需要使用模逆元來計算C(a, b) fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD。5.3 圖模型的構建與特殊情況自環如果存在i使得g(i) i那么邊(i, i)是一個自環。在環的匹配中自環不能被選取因為選了就意味著p[i]i但我們的目標是計算違反約束的情況這里需要仔細理解。在我們的容斥模型中M(k)是從禁止邊中選k條形成一個匹配。如果有一條自環邊它自己就是一個匹配大小為1。但在環的DP中自環需要特殊處理。通常如果g是置換不會有自環除非是恒等映射即錯位排列情況我們已單獨處理。如果題目中出現了自環需要單獨考慮該點。多連通分量g(i)可能將圖分解為多個不相交的環或鏈。例如g(i) i1當i為奇數g(i)i-1當i為偶數這會形成多個長度為2的環。此時總M(k)是各個分量匹配數的卷積。設第j個分量的生成函數為G_j(x) Σ_t f_component_j(t) * x^t那么總生成函數G(x) Π_j G_j(x)。M(k)就是G(x)中x^k的系數?？梢杂肈P卷積來計算dp[i][k]表示考慮前i個分量總共選了k條邊的方案數dp[i][k] Σ_{t0}^{min(k, max_t_i)} dp[i-1][k-t] * f_i(t)其中f_i(t)是第i個分量上選t條邊的方案數。n1 的邊界情況務必單獨處理n1。根據g(1)的定義判斷是否存在有效排列。通常如果g(1)1則禁止p[1]1但排列只有[1]故答案為0。如果g(1)不等于1或不在值域內則答案為1。5.4 性能優化與調試打印中間結果對于小的n如n5可以手動枚舉所有排列驗證你的程序輸出。計算M(k)、F(k)的值看是否符合預期。使用動態規劃打表如果組合數公式讓你不放心可以用DP直接計算f_chain和f_cycle。例如# 鏈的匹配數DP f_chain_dp [[0]*(n1) for _ in range(n1)] for m in range(n1): f_chain_dp[m][0] 1 for t in range(1, (m1)//21): # 不選第一條邊: f_chain(m-1, t) # 選第一條邊: 則不能選第二條邊轉為 f_chain(m-2, t-1) f_chain_dp[m][t] (f_chain_dp[m-1][t] (f_chain_dp[m-2][t-1] if m2 and t1 else 0)) % MOD環的DP也可以用類似方法打表。模運算全程注意取模特別是在做減法和乘法時。(a - b) % MOD應該寫成(a - b MOD) % MOD來避免負數。5.5 從本題延伸出去的思考“Good Permutations”問題是一個很好的組合數學訓練場。它教會我們將計數問題轉化為圖論模型通過“禁止邊”構建二分圖將排列約束轉化為圖上的匹配問題。熟練運用容斥原理化“全體滿足”為“至少違反一個”的補集通過固定違反約束來簡化問題。掌握經典模型的計算鏈和環上的匹配計數是經典問題其結論和遞推式應當熟記。處理復雜情況的分治思想對于多個連通分量分別求解再合并。當你掌握了這個框架后可以嘗試解決更復雜的變種例如雙重禁止p[i] ! a[i]且p[i] ! b[i]。部分位置無約束有些位置i沒有禁止條件。求字典序第K大的好排列結合計數和構造。解決這些問題都需要你在上述核心思路的基礎上進行靈活的調整和擴展。最重要的是保持清晰的數學模型并耐心地推導和驗證。