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