HNOI 2009 有趣的數列：卡特蘭數與質因數分解優化詳解

題目背景與定義

這是一道經典的組合數學問題，源自 HNOI 2009。我們稱一個長度為 2n 的數列為「有趣的數列」，當且僅當滿足三個條件：

1. 它是 1 到 2n 這 2n 個整數的一個排列 {a_i}；
2. 所有奇數項遞增：a₁ < a₃ < … < a₂ₙ₋₁，所有偶數項遞增：a₂ < a₄ < … < a₂ₙ；
3. 任意相鄰兩項 a₂ᵢ₋₁ 與 a₂ᵢ（1 ≤ i ≤ n）滿足奇數項小於偶數項，即 a₂ᵢ₋₁ < a₂ᵢ。

目標是對給定的 n，求出不同的長度為 2n 的有趣數列個數，答案對 P 取模。輸入範圍：n ≤ 1,000,000，P ≤ 1,000,000,000。

數學轉化：卡特蘭數

經過分析可知，這個問題的答案正是第 n 個卡特蘭數：

Cₙ = (1/(n+1)) × C(2n, n) = (2n)! / (n! × (n+1)!)

對於樣例 n=3，C₃ = 5，與題目給出的 5 個數列完全吻合。

核心挑戰：大數階乘的模運算

直接計算階乘會溢位，且 P 不一定是質數，無法使用費馬小定理求逆元。必須採用質因數分解的方法：

• 將分子 (n+2) 到 2n 的所有整數質因數分解，指數累加；
• 將分母 2 到 n 的所有整數質因數分解，指數扣減；
• 最後將所有質數的冪次相乘，過程中對 P 取模。

優化演進：從 O(n log n) 到 O(n)

初始版本：歐拉篩 + 逐個分解

先用歐拉篩法 O(n) 求出 2n 以內所有質數，再枚舉每個數進行試除分解。雖然正確，但對 n=10⁶ 會超時。

優化 1：合數分解遞推

觀察到：若已知合數 x 的一個質因子 p，則 x/p 的分解結果已知。可以從大到小枚舉，將合數的指數「推」給其因子：

f[因子] += f[合數]
f[合數/因子] += f[合數]

直到遇到質數為止，避免重複試除。

優化 2：單次循環初始化

將 2~n 的指數初始化為 -1（分母），n+2~2n 初始化為 +1（分子），再從 2n 遞減到 2 執行分解遞推，只需一輪循環。

最終 AC 代碼精要

for (i = 2; i <= 2*n; i++) {
    if (!come[i]) prime[++cnt] = i;
    for (j = 1; j <= cnt && prime[j]*i <= 2*n; j++)
        come[prime[j]*i] = i;  // 記錄最小質因子
}
for (i = 2; i <= n; i++) a[i] = -1;
for (i = n+2; i <= 2*n; i++) a[i] = 1;
for (i = 2*n; i > 1; i--)
    if (come[i]) {  // 合數
        a[come[i]] += a[i];
        a[i/come[i]] += a[i];
    } else {  // 質數
        temp = temp * pow(i, a[i]) % mod;
    }

時間複雜度 O(n)，空間 O(n)，完美通過 10 秒時限。

總結與啟發

這道題展示了「數學建模 → 組合恆等式 → 質因數分解 → 線性篩優化」的完整解題鏈路。關鍵在於將「逐個分解」轉化為「自底向上遞推」，這是處理大範圍階乘模運算的通用技巧。