SERC 2013 E 摩天大樓：排列組合與可見性計數

問題背景

摩天大樓是一款經典的鉛筆謎題，玩法是在一個 n×n 的方格棋盤上進行。每個格子代表一棟建築，高度從 1 到 n 各不相同。每行和每列必須包含高度 1 到 n 的建築各一棟。棋盤邊緣標有數字，表示從該方向望過去能看到多少棟建築——較高的建築會遮擋較矮的建築。給定邊緣的數字，玩家需推算出每個格子的建築高度。

核心問題

考慮謎題中的單行：已知從左側可見 left 棟建築，從右側可見 right 棟，試問有多少種方式將高度 1 到 n 的建築填入該行？這實質上是在詢問：在 1..n 的排列中，滿足左可見數為 left、右可見數為 right 的排列個數。

輸入輸出規範

• 多組測試資料，每行三個整數 n left right（1 ≤ n ≤ 5000）。
• 以 0 0 0 結束。
• 對每組資料，輸出滿足條件的排列數，模 1,000,000,007。

範例

輸入：
3 2 2
4 1 2
0 0 0

輸出：
2
2

解題思路

這是一個經典的動態規劃問題。定義 dp[i][j][k] 為長度為 i 的排列中，左可見 j 棟、右可見 k 棟的方案數。轉移方程考慮將最大值 n 放在不同位置，將問題分解為左右兩個子問題。利用組合數 C(n-1, pos-1) 選擇左側元素，乘以左子問題與右子問題的方案數累加。預處理組合數與 DP 表，單次查詢 O(1)。

關鍵代碼片段

const long long MOD = 1000000007;
LL s[5050][5050], c[5050][5050];

void init() {
    for(int i=0; i<5050; i++) c[i][i]=c[i][0]=1;
    for(int i=2; i<5050; i++)
        for(int j=1; j

複雜度分析
預處理 O(n²)，查詢 O(1)，空間 O(n²)。n ≤ 5000 時約 2500 萬狀態，內存約 200 MB，需優化為滾動數組或短整型存儲。