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