首页 > 试题广场 >

N个人参加比赛

[问答题]

【编程】

N个人参加比赛，进行排名，每个名次都可以并列，总共有多少种排列方法。例如：ABC个人参加比赛，比赛名次可以如下：1） A第一名、B第二名、C第三名 2）AB并列第一名，C第二名，等等。总共有13种排列方法。
输入，例如
2   //第一行为测试用例数目
1   //参加的人数1
3   //参加的人数3
输出(结果对10000取模)
1
13
添加回答
⎝≧⏝⏝≦⎠|头像 ⎝≧⏝⏝≦⎠|
排列组合题，输入n，最后的结果为A（n,1）+A（n,2）+...+A（n,n）
发表于 2017-08-05 16:25:21 回复(0)
秒速__五厘米头像 秒速__五厘米
排列组合 1 A（1，1） 2 A（2，2） 3 A（3，3）+C（3，1）*A（2，2）+A（1，1） 4 A（4，4）+C（4，2）*A（3，3） +C（4，1）*A（2，2）+A（1，1）
发表于 2017-08-07 16:22:32 回复(1)
刘二毛头像 刘二毛
//动态规划
int fij(int i, int j){
int res = 1;
if (i == 0 || j == 0 || i > j) return 0;
if (i == j){
while (i > 1){
res = i*res;
i--;
}
return res;
}
res = i * fij(i, j - 1) + i * fij(i - 1, j - 1);
return res;
}

int kindnums(int n){
if (n == 0) return 0;
if (n == 1) return 1;
int times = n;
int res = 0;
int i = 1;
while (i <= n){
res = res + fij(i, n);
if (res >= 10000) res = res % 10000;
i++;
}
return res;
}

int main(){
int len, tmp;
cin >> len;
vector<int> nums;
for (int i = 0; i < len; i++){
cin >> tmp;
nums.push_back(tmp);
}
for (int i = 0; i < len; i++){
tmp = nums[i];
cout << kindnums(tmp) << endl;;
}
system("pause");
}


//////////////////////////////////////////////////////////////
long long dp[10000][10000];

long fact(int n){
if (n == 0) return 0;
long res = 1;
while (n > 0){
res = n * res;
n--;
}
return res;
}

int solve(int n){
if (n > 10000) return 0;
for (int j = 1; j <= n; j++){
for (int i = 1; i <= j; i++){
if (i == 1) dp[i][j] = 1;
else if (i == j) dp[i][j] = fact(i);
else dp[i][j] = i*dp[i][j - 1] + i * dp[i - 1][j - 1];
}
}
}

int main(){
int len, tmp;
cin >> len;
int res = 0;
vector<int> nums;
for (int i = 0; i < len; i++){
cin >> tmp;
nums.push_back(tmp);
}
for (int i = 0; i < len; i++){
solve(nums[i]);
int tmp = nums[i], n = nums[i];
while (tmp > 0){
res = res + dp[tmp--][n] % 10000;
res = res % 10000;
}
cout << res << endl;
}
system("pause");
return 0;
}
编辑于 2017-08-06 11:24:22 回复(1)
提交观点

问题信息

C++ Java Javascript C# Python
来自：猎豹移动2017秋招开...
上传者：牛妹
难度：
3条回答 6572浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号