爱奇艺-笔试刷题2018-07-12

题目描述：

/**
时间限制：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;
}