UVA 12034 Race：動態規劃計算馬匹排名方案數（含模數運算）

題目大意

有 n 匹馬比賽，允許並列名次。求所有可能的排名情況總數（模 10056）。例如 2 匹馬：[1,2]、[2,1]、[1,1] 共 3 種。

動態規劃模型

狀態定義

dp[i][j]：前 i 匹馬形成 恰好 j 個不同名次 的方案數。

轉移方程推導

考慮第 i 匹馬加入：

1. 單獨形成新名次：前 i-1 匹馬有 j-1 個名次，第 i 匹馬插入 j 個可能位置（最前、各名次間、最後）→ j * dp[i-1][j-1]。
2. 併入現有名次：前 i-1 匹馬已有 j 個名次，第 i 匹馬選擇其中一個名次並列 → j * dp[i-1][j]。

合併：

dp[i][j] = j * (dp[i-1][j-1] + dp[i-1][j])  (mod 10056)

邊界與初始化

• dp[0][0] = 1（0 匹馬 0 個名次，1 種方案）。
• dp[i][0] = 0 for i > 0。
• j 範圍：1 ≤ j ≤ i。

最終答案

ans[n] = Σ dp[n][j]  (1 ≤ j ≤ n)  (mod 10056)

完整程式碼（預處理所有 n ≤ 1000）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 10056;
const int MAXN = 1000;
int dp[MAXN+1][MAXN+1];
int ans[MAXN+1];

void init() {
    dp[0][0] = 1;
    for (int i = 1; i <= MAXN; ++i) {
        int sum = 0;
        for (int j = 1; j <= i; ++j) {
            dp[i][j] = (int)((1LL * j * (dp[i-1][j-1] + dp[i-1][j])) % MOD);
            sum += dp[i][j];
            if (sum >= MOD) sum -= MOD;
        }
        ans[i] = sum;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    init();
    int T; cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        int n; cin >> n;
        cout << "Case " << cas << ": " << ans[n] << '\n';
    }
    return 0;
}

複雜度分析

• 預處理：O(MAXN²) = 10⁶ 操作，極快。
• 查詢：O(1)。
• 空間：O(MAXN²) 整數陣列 ≈ 4MB。

數學背景：有序貝爾數

本題求的是 有序貝爾數，又稱 Fubini 數。其指數生成函數為 1/(2 - eˣ)。遞推式也可寫為：

a(n) = Σ_{k=1..n} C(n,k) * a(n-k),  a(0)=1

但本題 DP 方案更直觀易實作。

測試樣例

常見坑點

• 模數運算中 j * (a+b) 可能溢位 int，需用 1LL * j * ... 提升至 long long。
• 題目要求輸出格式 Case X: Y，大小寫與冒號空格需完全一致。
• 預處理上限 1000 足夠，題目 n ≤ 1000。

總結

UVA 12034 是經典的**有序集合分割計數**問題，利用 DP 狀態 dp[i][j] 表示「前 i 個元素分成 j 組」的有序分割數，轉移邏輯清晰對應「新建組」與「併入現有組」兩種選擇。預處理 + O(1) 查詢完美應對多測資場景。