POJ 1037 可愛的木柵欄：歐拉數 DP + 字典序第 k 個波浪排列構造

dp[n][k][0] = Σ dp[n-1][j][1]  (j = k .. n-1)   // 注意：剩餘數重新排序後的排名
dp[n][k][1] = Σ dp[n-1][j][0]  (j = 1 .. k-1)

初始條件

dp[1][1][0] = dp[1][1][1] = 1;

構造第 C 個排列

從左到右貪心決定每位：

1. 維護 used[] 標記已用數字
2. 第 i 位嘗試候選數 x (按值從小到大)：
   • 若 x 未用，計算以 x 為第 i 位的合法排列數 cnt
   • 若 累積 + cnt < C，累積加上 cnt，繼續試下一個 x
   • 否則 x 即為第 i 位答案，固定之，進入第 i+1 位

計算 cnt 時需根據已確定的前綴趨勢判斷：

• i=1：cnt = dp[n][rank][0] + dp[n][rank][1] (rank 為 x 在剩餘數中的排名)
• i>1 且上一趨勢 UP (a[i-2] < a[i-1])：當前必須 DOWN → cnt = dp[rem][rank][1]
• i>1 且上一趨勢 DOWN：當前必須 UP → cnt = dp[rem][rank][0]

完整代碼

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int MAXN = 25;
int64 dp[MAXN][MAXN][2]; // dp[len][rank][dir] 0=UP, 1=DOWN

void initDP() {
    memset(dp, 0, sizeof(dp));
    dp[1][1][0] = dp[1][1][1] = 1;
    for (int n = 2; n <= 20; ++n) {
        for (int k = 1; k <= n; ++k) { // 首元素為第 k 小
            // UP: 第二個 > 首元素 → 剩餘中選排名 k..n-1 的數，新趨勢 DOWN
            for (int j = k; j <= n-1; ++j) dp[n][k][0] += dp[n-1][j][1];
            // DOWN: 第二個 < 首元素 → 剩餘中選排名 1..k-1，新趨勢 UP
            for (int j = 1; j <= k-1; ++j) dp[n][k][1] += dp[n-1][j][0];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    initDP();

    int T;
    cin >> T;
    while (T--) {
        int n; int64 c;
        cin >> n >> c;

        vector ans(n+1);
        vector used(n+1, false);

        for (int i = 1; i <= n; ++i) {
            int64 accum = 0;
            // 枚舉候選值 v 從 1 到 n
            for (int v = 1; v <= n; ++v) {
                if (used[v]) continue;

                // 計算 v 在剩餘數中的排名 (1-based)
                int rank = 0;
                for (int u = 1; u <= v; ++u) if (!used[u]) ++rank;

                int rem = n - i + 1;
                int64 cnt = 0;

                if (i == 1) {
                    cnt = dp[rem][rank][0] + dp[rem][rank][1];
                } else {
                    bool lastUp = (ans[i-2] < ans[i-1]);
                    if (lastUp) cnt = dp[rem][rank][1]; // 需 DOWN
                    else cnt = dp[rem][rank][0];        // 需 UP
                }

                if (accum + cnt >= c) {
                    ans[i] = v;
                    used[v] = true;
                    break;
                }
                accum += cnt;
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (i > 1) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

複雜度分析

• DP 預計算：O(N³) = 20³ = 8000，極快
• 構造排列：O(N²) (每位線性掃描排名)
• 空間：O(N²)
• 答案範圍：N=20 時總數 < 2⁶³，符合 long long

關鍵技巧總結

1. 相對排名 DP：狀態用「第 k 小」而非具體值，消除具體值依賴
2. 趨勢編碼：UP/DOWN 二狀態捕捉波浪交替本質
3. 字典序構造：貪心試值 + DP 計數跳過，標準「第 k 個排列」範式
4. 長長整型：N=20 總數 ≈ 7.4×10¹⁶，需 int64

相關概念

• 歐拉數 E_n = Σ_k dp[n][k][0] (或 [1])，計數所有波浪排列
• Entringer 數 E(n,k) = dp[n][k][0]
• OEIS A000111 (Up/down 數)

本題將組合計數、DP、貪心構造完美融合，是排列枚舉進階的經典範例。