UVA 12034 - Race

題目鏈接

題意：給定n匹馬，要求出可能的排名情況（可能並列）
思路：遞推，dp[i][j]表示i匹馬的時候有j種不同名次，那麼dp[i][j]可以由dp[i - 1][j - 1]插入j個不同位置得來，或者由dp[i - 1][j]放入已有j的名次得來，得到遞推式dp[i][j] = j * (dp[i - 1][j - 1] + dp[i - 1][j]); 然後對於n的答案為sum{dp[n][j]} (1 <= j <= n)
代碼：

#include 
#include 

const int MOD = 10056;

const int N = 1005;

int t, n, dp[N][N], ans[N];

void init() {
    dp[0][0] = 1;
    for (int i = 1; i <= 1000; i++) {
    int sum = 0;
    for (int j = 1; j <= i; j++) {
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD * j % MOD;
        sum = (sum + dp[i][j]) % MOD;
    }
    ans[i] = sum;
    }
}

int main() {
    int cas = 0;
    init();
    scanf("%d", &t);
    while (t--) {
    scanf("%d", &n);
    printf("Case %d: %d\n", ++cas, ans[n]);
    }
    return 0;
}