By admin
比赛排名
程序运行时间限制：1秒
问题描述：
N个同学参加一场比赛，比赛结果可能出现并列排名，问最终有多少种可能的不同排名结果。举例说明：假设有3个同学A, B和C参加比赛，则最终的排名结果：
可能是：第一名：B，第二名：C，第三名：A
也可能是：第一名：A和B并列，第二名C；
所有这些可能的不同排名结果共有13种。
输入描述：
第一行输入一个m表示有m组测试数据
以下m行，每行输入一个整数N，表示有N个同学参加比赛，1<=N<=100
输出描述：
输出对于N个同学，不同的排名结果数模10000（即取结果后4位），每个输出占一行
输入样例：
2
1
3
输出样例：
1
13
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAXN 1000
#define offset 10000
#define eps 1e-11
#define PI acos(-1.0)//3.14159265358979323846
#define exp 2.718281828
#define mod 1000000007
using namespace std;
typedef long long LL;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//f[i][j]为i个人分为j组
int f[101][101];
int main(int argc, char** argv) {
for(int i = 0;i<101;i++){
for(int j = 0;j<101;j++){
if(j < i || j<1){
f[i][j] = 0;
}
if(j == 1 && j<=i){
f[i][j] = 1;
}
if(j > 1 && j<=i){
f[i][j] = (f[i-1][j]+f[i-1][j-1])*j;
}
f[i][j] %= 10000;
}
}
int g;
scanf("%d",&g);
while(g--){
int n;
scanf("%d",&n);
int sum = 0;
for(int i = 1;i<=n;i++){
sum += f[n][i];
sum %= 10000;
}
printf("%d\n",sum);
}
return 0;
}