题目描述:
/**
时间限制:1秒
空间限制:32768K
牛牛养了n只奶牛,牛牛想给每只奶牛编号,这样就可以轻而易举地分辨它们了。
每个奶牛对于数字都有自己的喜好,
第i只奶牛想要一个1和x[i]之间的整数(其中包含1和x[i])。
牛牛需要满足所有奶牛的喜好,
请帮助牛牛计算牛牛有多少种给奶牛编号的方法,输出符合要求的编号方法总数。
输入描述:
输入包括两行,
第一行一个整数n(1 ≤ n ≤ 50),表示奶牛的数量
第二行为n个整数x[i](1 ≤ x[i] ≤ 1000)
输出描述:
输出一个整数,表示牛牛在满足所有奶牛的喜好上编号的方法数。
因为答案可能很大,输出方法数对1,000,000,007的模。
输入例子1:
4
4 4 4 4
输出例子1:
24
*/
思路如下:
对x[i]升序排序,然后按着升序顺序遍历
x[i]<=x[i+1]说明x[i]选择就会影响x[i+1]
对于x[i]来说其可以选择的位置只有 x[i]-i个位置
然后由乘法原理累乘即可得到全部组合
代码如下:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define MAX_N 55
#define MOD 1000000007
using namespace std;
int x[MAX_N];
int main()
{
int N;
scanf("%d", &N);
for(int i=0; i<N; i++)
scanf("%d", x+i);
sort(x, x+N);
long long res=1;
for(int i=0; i<N; i++){
if(x[i]<=i){
res=0;
break;
}
res*=(long long)(x[i]-i);
res%=MOD;
}
printf("%lld", res);
return 0;
}
网友评论