HDU 4372：第一類斯特林數組合應用

題目背景

給定 n 根高度互不相同的柱子，從前面看能看到 f 根，從後面看能看到 b 根。求排列數模 1e9+7。

組合推導

• 最高柱子必須被從前、後同時看到，將其作為分界。
• 剩下 n-1 根柱子分為 f+b-2 組「可見段」（第一類斯特林數 s(n-1, f+b-2)）。
• 從這些段中選 f-1 段分配到前面（其餘 b-1 段在後面），組合數 C(f+b-2, f-1)。
• 答案 = s(n-1, f+b-2) * C(f+b-2, f-1) % MOD。

第一類斯特林數遞推

s(n, k) = s(n-1, k-1) + (n-1) * s(n-1, k)
含義：第 n 個元素單獨成環（s(n-1,k-1)），或插入現有 n-1 個位置中的任意一個（(n-1)*s(n-1,k)）。

完整代碼

#include 
using namespace std;
const int MOD = 1e9+7;
const int MAXN = 2005;
long long s[MAXN][MAXN], C[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 預處理斯特林數
    s[0][0] = s[1][1] = 1;
    for (int i = 2; i < MAXN; ++i)
        for (int j = 1; j <= i; ++j)
            s[i][j] = (s[i-1][j-1] + (i-1) * s[i-1][j]) % MOD;
    // 預處理組合數
    for (int i = 0; i < MAXN; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
    int T; cin >> T;
    while (T--) {
        int n, f, b; cin >> n >> f >> b;
        if (f + b - 2 > n - 1) { cout << 0 << "\n"; continue; }
        long long ans = s[n-1][f+b-2] * C[f+b-2][f-1] % MOD;
        cout << ans << "\n";
    }
    return 0;
}

複雜度

• 預處理 O(N²)，N=2000 約 400 萬次運算，極快。
• 每查詢 O(1)。