題目鏈接：uva 12034 - Race

題目大意：有n匹馬比賽，問說有多少種排名情況，可以並列。

解題思路：dp[i][j]表示i匹馬，最後一名為j的情況，轉移方程dp[i][j]=(dp[i?1][j]+dp[i?1][j?1])?j

#include 
#include 

typedef long long ll;
const int N = 1005;
const ll MOD = 10056;
ll dp[N][N], f[N];

void init () {
    memset(f, 0, sizeof(f));
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;

    for (ll i = 1; i <= 1000; i++) {

        for (ll j = 1; j <= i; j++) {
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] * j) % MOD;
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * (j + 1)) % MOD;
            f[i] = (f[i] + dp[i][j]) % MOD;
        }
    }
}

int main () {
    init();
    int cas, n;
    scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        scanf("%d", &n);
        printf("Case %d: %lld\n", i, f[n]);
    }
    return 0;
}