Race LightOJ

题意：

  (t) 组数据，每组给出一个数 (n) 代表 (n) 匹马，两匹马之间进行赛跑有三种结局：同时到达、第一个先到第二个后到、第一个后到第二个先到，现在这 (n) 匹马赛跑，问有多少种情况?

分析：

(dp[i][j]) 表示 (i) 匹马，(j) 个排名的个数。
状态转移方程：
(dp[i][j]=dp[i-1][j-1]*j+d[i-1][j]*j)
即增加一匹马，要么排名数 (+1) ，要么不变。
预处理。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=10056;
int ans[1010],dp[1010][1010];
void init()
{
    dp[1][1]=1;
    ans[1]=1;
    for(int i=2;i<=1000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=(dp[i-1][j]*j%mod+dp[i-1][j-1]*j%mod)%mod;
            ans[i]=(ans[i]+dp[i][j])%mod;
        }
    }
}
int main()
{
    int t,n,cas=0;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("Case %d: %d
",++cas,ans[n]%mod);
    }
    return 0;
}