题目问N匹马比赛有多少种结果。一开始想用排列组合搞搞，然后发现想错了。艰难地把思路转向DP，最后AC了。
- dp[i][j]表示前i匹马确定出j个名次的方案数
- dp[1][1]=1
- 对于第i匹马，它要确定出j个名次：要嘛前i-1匹确定出j个次名，然后第i匹可以成为第1...j名；要嘛前i-1匹确定出j-1个名次，然后第i匹成为独立的新的一个名次，也有第1..j名j种选择。
- 所以状态转移方程是：dp[i][j]=d[i-1][j]*j+d[i-1][j-1]*j
#include<cstdio>
#include<cstring>
using namespace std;
int d[][];
int main(){
d[][]=;
for(int i=; i<; ++i){
for(int j=; j<=i; ++j){
d[i][j]=d[i-][j]*j+d[i-][j-]*j;
d[i][j]%=;
}
}
int t,n;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%d",&n);
int res=;
for(int i=; i<=n; ++i){
res+=d[n][i];
res%=;
}
printf("Case %d: %d\n",cse,res);
}
return ;
}