【编程】
N个人参加比赛，进行排名，每个名次都可以并列，总共有多少种排列方法。例如：ABC个人参加比赛，比赛名次可以如下：1） A第一名、B第二名、C第三名 2）AB并列第一名，C第二名，等等。总共有13种排列方法。
输入，例如2 //第一行为测试用例数目
1 //参加的人数1
3 //参加的人数3
输出(结果对10000取模)
1
13
//动态规划
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)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
