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 <stdio.h>
#include <string.h>

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;
}