1359. Count All Valid Pickup and Delivery Options

Count All Valid Pickup and Delivery Options

題目描述： 給定 n 個訂單，每個訂單有取件（Pickup）和送達（Delivery）兩個事件。取件必須在對應的送達之前發生。求所有合法的事件排列數量（結果取模 10^9+7）。

解題思路： 使用組合數學推導。假設已有 i-1 個訂單的合法排列（共 2(i-1) 個事件），現在插入第 i 個訂單的 P_i 和 D_i。此時序列有 2(i-1)+1 = 2i-1 個可插入的間隙。

• P_i 有 2i-1 個位置可選。
• P_i 放好後，D_i 必須在 P_i 之後，所以 D_i 有 1 到 2i-1 個位置可選（取決於 P_i 的位置）。平均下來，D_i 有 (2i-1+1)/2 * ... 但更精確地：P_i 放在某位置後，D_i 可選的位置數等於 P_i 右邊（含 P_i 之後新增的位置）的數量。加總所有情況，恰好為 (2i-1) * i，也可以理解為 (2i-1) * 2i / 2。

因此遞推公式為：f(i) = f(i-1) * (2i-1) * i，其中 f(1) = 1。

時間複雜度：O(n) — 單次迴圈從 2 到 n。

空間複雜度：O(1) — 只使用常數額外空間。

直接階乘法：答案等於 (2n)! / 2^n，因為 2n 個事件的全排列中，每個訂單的 P 和 D 有 1/2 機率滿足 P 在 D 前面，共 n 個獨立約束。需要模逆元計算，實作較複雜。

動態規劃：定義 dp[i] 為 i 個訂單的合法排列數。遞推 dp[i] = dp[i-1] * (2i-1) * i。與迭代法本質相同，但用陣列儲存中間結果。空間 O(n)。

1. 若有些訂單之間有優先順序約束（訂單 A 必須在訂單 B 之前完成），如何修改？
2. 若每個訂單可以有多個中繼點（不只是取件和送達），組合數如何變化？
3. 如何直覺理解 (2n)! / 2^n 這個公式的含義？