首页 > 试题广场 >

奶牛编号

[编程题]奶牛编号

热度指数：5390 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛养了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

输出

算法知识视频讲解

牛客1659416

先给x[i]最小的奶牛(假设为 i1 )编号，共有x[ i1 ]种编号方法，然后给x[i]第二小的奶牛(假设为 i2 )编号，这时共有x[i2]-1种编号方法(因为 i1 已经先选走了 1 个编号)，接着给x[i]第三小的奶牛(假设为 i3 )编号，此时共有x[i3]-2种编号方法(因为 i1和i2已经选走了 2 个编号)...

所以编号方法总数为 x[i1]*(x[i2]-1)*(x[i3]-2)*...*(x[in]-(n-1))。

可以先对x[i]按从小到大排好序，所以编号方法总数为x[0]*(x[1]-1)*(x[2]-2)*...*(x[n-1]-(n-1))。


	#include <iostream>



	#include <algorithm>



	using namespace std;



	long long mod=1000000007;



	int main()



	{



	    int n;



	    while( cin >> n )



	    {



	        int a[n];



	        for(int i=0; i<n; i++)



	            cin >> a[i];



	        sort(a,a+n);



	        long long counts=1;



	        for(int i=0; i<n; i++)



	        {



	            counts=((a[i]-i)*counts)%mod;



	        }



	        cout << counts << endl;



	    }



	}

编辑于 2018-03-30 17:57:08 回复(2)

元气の悟空

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    int n,i,x,a[100];
    long long res=1,mod=1000000007;
    for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",a+i);
    for(sort(a,a+n),i=0;i<n;i++) res=res%mod*(a[i]-i)%mod;
    printf("%lld",res);
}

发表于 2017-11-29 12:37:56 回复(3)

C/C++

霍七

本套3道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)，牛客网上的其他题目解答也在持续更新。

#include <iostream>
#include <algorithm>
#define mod 1000000007
using namespace std;
int main()
{
    int n; cin >> n;
    int *num = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    sort(num, num + n);
    long long int result = 1;
    for (int i = 0; i < n; i++) {
        if (num[i] <= i) {
            cout << 0 << endl;
            return 0;
        }
        result = result*(num[i] - i) % mod;
    }
    cout << result << endl;
    delete[] num;
    return 0;
}

编辑于 2017-12-21 10:44:39 回复(3)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

const int M = 1e9+7;
int main(){
    int n;
    long s=1;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    sort(a, a+n);
    for(int i=0;i<n;i++)
        s = (s*(a[i]-i)) % M;
    printf("%ld\n", s);
    return 0;
}

发表于 2020-10-18 10:56:05 回复(0)

Java

Mono_Chrome

import java.util.Arrays;
import java.util.Scanner;

public class Main {


    public static final long MAX = 1000000007;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);
        long res = 1;
        for (int i = 0; i < n; i++) {
            res *= (arr[i] - i) % MAX;
            res %= MAX;
        }
        System.out.println(res);
    }
}

发表于 2019-06-15 18:31:51 回复(0)

Java

成程晨

import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            int n = in.nextInt(),i = 0;
            int[] a = new int[n];
            while(i < n){
                a[i++] = in.nextInt();
            }
            System.out.println(helper(a));
        }
    }
    public static long helper(int[] a){
        long res = 1;
        Arrays.sort(a);
        int c = 0;
        for(int num:a){
            res = (res * ((num - c++) % 1000000007)) % 1000000007; //先取余再乘再取余  不用等最后结果再取余
        }
        return res;
    }
}

发表于 2019-02-11 19:56:33 回复(0)

Alejandro1

#include<iostream>
#include<algorithm>

using namespace std;

long long mod = 1000000007;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    long long counter = 1;
    for (int i = 0; i < n; i++) {
        counter = ((a[i] - i)*counter)%mod;
    }
    cout << counter << endl;
    return 0;
}

发表于 2019-01-28 01:17:57 回复(0)

喝可乐不如喝开水

n=int(raw_input())
m=map(int,raw_input().strip().split())
m.sort()
k=1
for i in range(n):
k=(m[i]-i)*k
print k%1000000007

发表于 2018-06-27 09:58:45 回复(0)

向宇回桌

把奶牛所希望的编号排个序，然后就是乘法原理了。

比如 4 3 9 6，排序为3 4 6 9。第一个奶牛有3种取法，第二只奶牛有(4-1)种取法，第三头奶油有(6-2)种取法，第四匹奶牛就有9-3种取法。

import java.util.*;

public class Main {
    private static final long MOD = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i=0; i!=n; i++) {
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums);
        long ans = 1;
        for (int i=0; i!=n; i++) {
            ans *= ((nums[i] - i) % MOD);
            ans %= MOD;
        }
        System.out.println(ans);
    }
}

发表于 2019-03-02 19:01:37 回复(3)

何处理红绡丶

import java.math.BigInteger;
import java.util.*;

public class TheCowNumber {
    static final int mod = 1000000007;
    public static void main(String[] args) {
        /**
         * 本题重点在于如何处理大数。而不是算法。
         * 算法很简单，就是排序，每选一个数，后一个可选择的就减一
         */
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Integer array[] = new Integer[n];
        for(int i=0;i < n;i ++){
            array[i] = scanner.nextInt();
        }
        Arrays.sort(array);
        BigInteger result = new BigInteger("1");
        for(int i=0;i <array.length;i ++){
            int tmp = array[i] - i;
            String s = tmp + "";
            result = result.multiply(new BigInteger(s));
        }
        String mod = 1000000007 + "";
        System.out.println(result.mod(new BigInteger(mod)));
    }
}

发表于 2020-03-18 10:51:36 回复(0)

阿耀哥

参考向宇回桌的思路写的代码

n=int(input())
s=list(map(int,input().split()))
s.sort()
result=1
for x in range(n):
    result *= s[x]-x
print(result%1000000007)

发表于 2020-02-06 18:04:19 回复(0)

冲刺Offer_yy

n =int(input().strip())

data =list(map(int, input().strip().split(' ')))

data.sort()

count =1

fori inrange(len(data)):

m =data[i] -i

count =count *m

print(count%1000000007)

发表于 2019-09-18 18:34:05 回复(0)

魏无忌

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    int N;
    vector<int> X;
    cin >> N;
    for(int i = 0; i < N; i++){
        int temp;
        cin >> temp;
        X.push_back(temp);
    }
    sort(X.begin(), X.end());
    for(int i=0; i < N; i++){
        X[i] -= i;
    }
    long long product = 1;
    for(int i = 0; i < N; i++){
        product = product * X[i] % 1000000007;
    }
    cout << product;
    return 0;
}

发表于 2019-09-18 16:45:47 回复(0)

我要扛offer回家

import sys
n=int(sys.stdin.readline().strip())
x=list(map(int,sys.stdin.readline().split()))
x.sort()
res=1
for i in range(len(x)):
    res=res*(x[i]-i)
print(res%(1000000007))

发表于 2019-09-17 23:59:01 回复(0)

Belladonna

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define mod 1000000007;
int main()
{
int n;
while(cin>>n)
{
int i;
int X[1000];
for(i=0;i<n;i++)
{
cin>>X[i];
}
sort(X,X+n);
long long ans=1;
for(i=0;i<n;i++)
{
ans=(ans*(X[i]-i))%mod;
}
cout<<ans<<"\n";
}
return 0;
}

发表于 2019-09-17 17:32:40 回复(0)

AyaBrea

要是所有公司出的算法题都跟爱奇艺的算法题一样就好了=。=

def solution():
    n = int(input())
    line = list(map(int, input().strip().split()))
    if not line:return None
    line.sort()
    res = 1
    for i in range(n):
        tmp = line[i] - i
        res *= tmp
    return res % 1000000007

if __name__ == '__main__':
    s = solution()
    print(s)

发表于 2019-09-06 21:09:43 回复(0)

嘎嘎嘎~


import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            CAL(sc);
        }
    }
    public static void CAL(Scanner sc){
        int n=sc.nextInt();
        int[] x=new int[n];
        for (int i=0;i<n;i++){
            x[i]=sc.nextInt();
        }
        Arrays.sort(x);
        long R=1;
        for(int i=0;i<n;i++){
            R=(R%1000000007)*(x[i]-i);//这里直接取余再接着乘，不要等最后结果再乘
        }
        System.out.println(R);
    }
}

发表于 2019-06-10 16:19:09 回复(0)

Python

Re:煙花ゼロから易冷

n = int(input())
x = list(map(int, input().split()))
x.sort()
out = x[0]
for i in range(1,len(x)):
    out = out * (x[i]-i)
print(out%1000000007)

发表于 2019-04-29 11:36:57 回复(0)

C/C++

韦禹

#include<iostream>

#include<vector>

#include<algorithm>

usingnamespacestd;

longlongT(intn,vector<int>& v){

sort(v.begin(),v.end());

longlongsum=1,mod=1000000007;

for(inti=0;i!=n;++i){

sum=sum%mod*(v[i]-i)%mod;

}

returnsum;

}

intmain(){

intn;vector<int> v={};cin>>n;

for(inti=0;i!=n;++i){

intt;cin>>t;v.push_back(t);

}

cout<<T(n,v);

}

发表于 2019-04-29 09:29:55 回复(0)

_OffeR++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a;
    vector<int>v;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    long long sum=1,mod=1000000007;
    for(int i=0;i<n;i++)
    {
        sum=sum%mod*(v[i]-i)%mod;
    }
    cout<<sum;
    return 0;
}

发表于 2019-04-10 15:16:10 回复(0)