Cerinta completa

Tara has an array, , consisting of integers where each integer occurs at most times in the array.

Let’s define to be a permutation of where is the element of permutation . Tara thinks a permutation is beautiful if there is no index such that where .

You are given queries where each query consists of some array . For each , help Tara count the number of possible beautiful permutations of the integers in and print the count, modulo , on a new line.

Note: Two permutations, and , are considered to be different if and only if there exists an index such that and .

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query in the following form:

  1. The first line contains an integer, , denoting the number of elements in array .
  2. The second line contains space-separated integers describing the respective values of in array .

Constraints

  • Each integer in can occur at most times.

For of the maximum score:

  • The sum of over all queries does not exceed .

For of the maximum score:

Output Format

For each query, print the the number of possible beautiful permutations, modulo , on a new line.

Sample Input 0

3
3
1 1 2
2
1 2
4
1 2 2 1

Sample Output 0

1
2
2

Explanation 0

We perform the following queries:

  1. Array and there is only one good permutation:
    image
    Thus, we print the result of on a new line.

  2. Array and there are two good permutations:
    image
    Thus, we print the result of on a new line.

  3. Array and there are two good permutations:
    image
    For demonstration purposes, the following two permutations are invalid (i.e., not good):
    image
    Because we only want the number of good permutations, we print the result of on a new line.

Limbajul de programare folosit: cpp14

Cod:

#include<stdio.h>
#include<stdlib.h>
#define m 1000000007u
#define m2 500000004u
typedef long long unsigned llu;
typedef unsigned u;
int S(const void*x,const void*y){return*(int*)x-*(int*)y;}
u C[2222][2222],A[2222],F[2222];
u P(u b,u e)
{
    u r=1;
    for(;e;e>>=1)
    {
        if(e&1)r=r*(llu)b%m;
        b=b*(llu)b%m;
    }
    return r;
}
int main()
{
    u t,n,i,j,k,d,r;
    for(i=-1;++i<2222;)for(C[i][j=0]=1;j++<i;)
    if((C[i][j]=C[i-1][j-1]+C[i-1][j])>=m)C[i][j]-=m;
    for(F[i=0]=1;++i<2222;)F[i]=i*(llu)F[i-1]%m;
    for(scanf("%u",&t);t--;)
    {
        scanf("%u",&n);
        for(i=-1;++i<n;)scanf("%u",A+i);
        qsort(A,n,sizeof(u),S);
        for(i=d=0;++i<n;)d+=A[i]==A[i-1];
        k=P(m2,d);r=0;
        for(i=-1;++i<=d;)
        {
            j=C[d][i]*(llu)F[n-i]%m*(llu)k%m;
            if((k<<=1)>=m)k-=m;
            if(i&1)
            {
                if((r-=j)>m)r+=m;
            }
            else 
            {
                if((r+=j)>=m)r-=m;
            }
        }
        printf("%u\n",r);
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464650238

Link challenge: https://www.hackerrank.com/challenges/taras-beautiful-permutations/problem

Tara’s Beautiful Permutations