tarunreddy1018

Untitled

Oct 18th, 2018
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.Arrays;
  3. import java.util.HashMap;
  4. import java.util.Map;
  5. import java.util.PriorityQueue;
  6.  
  7. class Pair
  8. {
  9.     public long value;
  10.     public long count;
  11.  
  12.     public Pair(long value,long count)
  13.     {
  14.         this.value = value;
  15.         this.count = count;
  16.     }
  17. }
  18.  
  19. public class Main
  20. {
  21.     private static int MOD = 1000000007;
  22.  
  23.     private static long prefixNCR[];
  24.  
  25.     private static void preComputePrefixNCR(int size)
  26.     {
  27.         prefixNCR = new long[size+1];
  28.  
  29.         prefixNCR[0] = 1;
  30.         prefixNCR[2] = 1;
  31.         prefixNCR[4] = 3;
  32.  
  33.         for(int i = 6;i <= size;i += 2)
  34.         {
  35.             prefixNCR[i] = ((i-1) * prefixNCR[i-2])%MOD;
  36.         }
  37.     }
  38.  
  39.     private static long countPairings(long skillSet[],int persons)
  40.     {
  41.         HashMap<Long,Long> map = new HashMap<>();
  42.  
  43.         for(int i = 0;i < persons;i++)
  44.         {
  45.             if(map.containsKey(skillSet[i]))
  46.             {
  47.                 map.put(skillSet[i],map.get(skillSet[i])+1);
  48.             }
  49.             else
  50.             {
  51.                 map.put(skillSet[i],(long)1);
  52.             }
  53.         }
  54.  
  55.         PriorityQueue<Pair> pq = new PriorityQueue<>((Pair p1,Pair p2) -> {
  56.  
  57.             if(p1.value < p2.value)
  58.             {
  59.                 return 1;
  60.             }
  61.             else
  62.             {
  63.                 return -1;
  64.             }
  65.         });
  66.  
  67.         for(Map.Entry<Long,Long> entry : map.entrySet())
  68.         {
  69.             long value = entry.getKey();
  70.             long count = entry.getValue();
  71.  
  72.             pq.add(new Pair(value,count));
  73.         }
  74.  
  75.         long count = 1;
  76.  
  77.         while(!pq.isEmpty())
  78.         {
  79.             Pair max = pq.poll();
  80.  
  81.             if (max.count % 2 == 0)
  82.             {
  83.                 count = (count * prefixNCR[(int)max.count]) % MOD;
  84.             }
  85.             else
  86.             {
  87.                 count = (count * (max.count * prefixNCR[(int)(max.count - 1)]) % MOD) % MOD;
  88.  
  89.                 Pair secondMax = pq.poll();
  90.  
  91.                 if (secondMax.count % 2 != 0)
  92.                 {
  93.                     count = (count * (secondMax.count * prefixNCR[(int)(secondMax.count - 1)])%MOD) % MOD;
  94.                 }
  95.                 else
  96.                 {
  97.                     count = (count * secondMax.count) % MOD;
  98.  
  99.                     secondMax.count -= 1;
  100.  
  101.                     pq.add(secondMax);
  102.                 }
  103.             }
  104.         }
  105.  
  106.         return count;
  107.     }
  108.  
  109.     public static void main(String[] args) throws IOException
  110.     {
  111.         BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
  112.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  113.         StringBuilder outputString = new StringBuilder();
  114.  
  115.         preComputePrefixNCR(100000);
  116.  
  117.         int testCases = Integer.parseInt(br.readLine());
  118.  
  119.         while(testCases --> 0)
  120.         {
  121.             int persons = Integer.parseInt(br.readLine());
  122.  
  123.             long skillSet[] = Arrays.stream(br.readLine().split(" ")).mapToLong(c->Long.parseLong(c)).toArray();
  124.  
  125.             outputString.append(countPairings(skillSet,persons)).append("\n");
  126.         }
  127.  
  128.         bw.write(outputString.toString());
  129.         bw.close();
  130.     }
  131. }
RAW Paste Data