fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. /* Name of the class has to be "Main" only if the class is public. */
  6. class Ideone
  7. {
  8. 	static final int M = 1000000007;
  9. 	public static void main (String[] args) throws java.lang.Exception
  10. 	{
  11.  
  12. 		Scanner in  = new Scanner(System.in);
  13. 		int t = in.nextInt();
  14.  
  15. 		while(t-- > 0)
  16. 		{
  17. 			//System.out.println("********NEW TEST CASE************");
  18.  
  19. 			int n = in.nextInt();
  20. 			int[] cpy = new int[n];
  21. 			int[] s = new int[n];
  22. 			long pairs = 1;
  23.  
  24. 		//	Random rn = new Random();
  25.  
  26. 			for(int i = 0; i < n; i++)
  27. 			{
  28. 				cpy[i] = in.nextInt();
  29. 			}
  30.  
  31. 			Arrays.sort(cpy);
  32.  
  33. 			for(int i = 0; i < n; i++)
  34. 			{
  35. 				s[i] = cpy[n-1-i];
  36. 			}
  37.  
  38.  
  39. 			int[][] sc = new int[n][2];
  40. 			int j = 0;
  41. 			sc[j][1] = 1;
  42.  
  43. 			for(int i = 1; i < n; i++)
  44. 			{
  45.  
  46. 				sc[j][0] = s[i-1];
  47. 				if(s[i] == s[i-1])
  48. 				{
  49. 					if(sc[j][1]==0)
  50. 					{sc[j][1] = 2;}
  51. 					else
  52. 					{sc[j][1]++;}
  53. 				}
  54. 				else
  55. 				{
  56.  
  57. 					j++;
  58. 					sc[j][1] = 1;
  59. 				}
  60. 			}
  61.  
  62. 			sc[j][0] = s[n-1];
  63.  
  64.  
  65. 		/**
  66. 			System.out.println("\nPrinting SC");
  67. 			for(int i = 0; i < j+1; i++)
  68. 			{
  69. 				System.out.println(sc[i][0] + "  " +sc[i][1]);
  70. 			}
  71. 		**/
  72.  
  73.  
  74. 			for(int i = 0; i < j; i++)
  75. 			{
  76. 				if(sc[i][1] != 0){
  77. 				if(sc[i][1] == 1)
  78. 				{
  79. 					pairs = (pairs * sc[i+1][1])%M;
  80. 			//		System.out.println("80:::" + pairs);
  81. 					sc[i+1][1] = sc[i+1][1]-1;
  82. 				}
  83. 				else
  84. 				{
  85. 					if(sc[i][1]%2 == 0){
  86. 					pairs = (pairs * groupsoftwo(sc[i][1]))%M;
  87. 			//		System.out.println("87:::" + pairs);
  88. 					}
  89. 					else
  90. 					{
  91. 					pairs = (pairs * groupsoftwo(sc[i][1]) * sc[i+1][1])%M;
  92. 			//		System.out.println("92:::" + pairs);
  93. 					sc[i+1][1] = sc[i+1][1]-1;
  94. 					}
  95. 				}
  96. 				}
  97. 			}
  98.  
  99. 			if(sc[j][1] > 2){
  100. 			pairs = (pairs * groupsoftwo(sc[j][1]))%M;
  101. 			}
  102.  
  103. 			System.out.println(pairs);
  104.  
  105. 		}
  106. 	}
  107. 			static long groupsoftwo(long x)
  108. 		{
  109. 			if((x == 0)||(x == 1))
  110. 			{
  111. 				return 0;
  112. 			}
  113. 			long f=1;
  114. 			long pow = x/2;
  115.  
  116. 			for(long i = (pow+1), j = (pow+1); i <= x; i++)
  117. 			{
  118. 				j  = i;
  119. 				while(((j%2)==0) && pow>0)
  120. 				{
  121. 					j /= 2;
  122. 					pow--;
  123. 				}
  124. 				f = (f*j)%M;
  125.  
  126. 			}
  127.  
  128.  
  129. 			return f;
  130.  
  131. 		}
  132.  
  133.  
  134. }
Success #stdin #stdout 0.11s 2184192KB
comments (?)
stdin
copy 
6
4
2 2 2 2
6
2 2 2 2 2 2
8
2 2 2 2 2 2 2 2 
6
1 1 2 2 2 2
14
1 1 1 1 1 2 2 2 2 2 2 3 3 3
8
1 1 1 1 1 2 3 3
stdout
copy 
3
15
105
3
4050
15
https://ideone.com/NN1rqk
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!