Tara's Beautiful Permutations

This problem as seen in Hackerrank.
Here is problem statement.

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: 
   
   Thus, we print the result of  on a new line.
2. Array  and there are two good permutations: 
   
   Thus, we print the result of  on a new line.
3. Array  and there are two good permutations: 
   
   For demonstration purposes, the following two permutations are invalid (i.e., not good): 
   
   Because we only want the number of good permutations, we print the result of  on a new line.

==  editorial =============================================

I spent a lot of hours to understand this problem. At first, it looks to me combinatorics problems. But, it can be solved with dynamic programming with careful observation.

In this problem, we are only care about the number of one occurrence integer, and the number of two occurrence integer, and need to figure out how they are related.

Let's take a example for this.

We have an integer array {1,2,1,2,3,4}, this array have one of one occurrence integer, and two of two occurrence integers. Let that i and j, respectively, then i = 2 and j = 2.

Our purpose is to get dp(2,2).

From {1,2,1,2,3,4}, we have two cases to reduce the size. ( there are one more case though.)

First, remove an integer that occurs once, that result in {1,2,1,2,3}. And it becomes i=1, j=2. 

How many ways exist to do this? We have 3 and 4. It is equal to the number of i, i.e., 2.

So, we have to add this case to our answer. dp(1,2)*2.

Second, remove an integer that occurs twice, that result in {2,1,2,3,4}. And it becomes i=3, j=1. Since we removed only one of two occurrence integer, here it is 1, we left single "1". This "1" becomes one occurrence integer, which is added to i.

How many ways exist to do this? We have 1 and 2. It is equal to the number of j, i.e., 2.

So, we have to add this case to our answer. dp(3,1)*2.

But, in the second case, we only remove one of two occurrence integer, we need to drill down one more step there. We have {2,1,2,3,4}, and i=3, and j=1.

Let's remove an integer that occurs once. We can remove either 3 or 4. We cannot remove "1", because it is originally an integer that occurs twice.

How many ways exist to do this? We have 3 and 4. It is equal to the number of j, i.e., 2.

The result array is {2,1,2,3} if we remove 3.

So, we have a special case to add this to the answer. dp(2,1)*2 if we are drill down one more step.

Let's summarize what we worked on so far.

dp(2,2) = 0;

dp(2,2) = dp(2,2) + dp(1,2) * 2;

dp(2,2) = dp(2,2) + dp(3,1) * 2;

dp(3,1) = 0;

dp(3,1) = dp(3,1) + dp(2,1) * 2;

These are recursive calls, and further drill down. Also, we have two states for each i and j.

Some base case:

if (i==0 && j == 0) return 0;

if (i<0 0="" div="" j="" return="">

if (dp[i][j][state] != -1) return dp[i][j][state];

Let's make a pseudo code for this.

 mod = 10^9+7;  

 int[][][] dp = new int[2000][2000][2];  

 int solve(int i, int j, int state) {  

   if (i==0 && j==0) return 0;  

   if (i<0 || j<0) return 0;  

   if (dp[i][j][state] != -1) return dp[i][j][state];  

   else {  

     int count = 0;  

     if (flag == 1) {  

      count = (count + (solve(i-1,j,0)*(i-1))%mod)%mod;  

     } else {  

      count = (count + (solve(i-1,j,0)*i)%mod)%mod;  

     }  

     count = (count + (solve(i+1,j-1)*j)%mod)%mod;  

     dp[i][j][state] = count;  

     return count;  

   }  

 }