*ASSIGN - Assignments ( bitmasking dp )

*ASSIGN - Assignments 

ASSIGN - Assignments

#dynamic-programming

Problem

Your task will be to calculate number of different assignments of n different topics to n students such that everybody gets exactly one topic he likes.

Input

First line of input contains number of test cases c (1<=c<=80). Each test case begins with number of students n (1<=n<=20). Each of the next n lines contains n integers describing preferences of one student. 1 at the ith position means that this student likes ith topic, 0 means that he definitely doesn't want to take it.

Output

For each test case output number of different assignments (it will fit in a signed 64-bit integer).

Example

Input:
3
3
1 1 1
1 1 1
1 1 1
11
1 0 0 1 0 0 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 0 0 
1 0 0 1 0 0 1 1 0 1 0 
1 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 0 0 1 1 1 
1 1 1 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 1 0 0 0 1 
1 0 1 1 0 0 0 0 0 0 1 
0 0 1 0 1 1 0 0 0 1 1 
1 1 1 0 0 0 1 0 1 0 1 
1 0 0 0 1 1 1 1 0 0 0 
11
0 1 1 1 0 1 0 0 0 1 0 
0 0 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 0 0 0 0 1 0 
0 1 0 1 0 1 0 1 0 1 1 
1 0 0 1 0 0 0 0 1 0 1 
0 0 1 0 1 1 0 0 0 0 1 
1 0 1 0 1 1 1 0 1 1 0 
1 0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 1 1 1 1 
0 1 0 0 0 0 0 0 0 1 1 
0 1 1 0 0 0 0 0 1 0 1 

Output:
6
7588
7426

-------------------------------------------------EDITORIAL-------------------------------------------------

SIMPLE BITMASKING DP

----------------------------------------CODE-----------------------------------------------------

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli dp[1<<21];
 int n;
 int maxi;
 int arr[21][21];
lli solve(int mask,int next)
 {
   if(mask==maxi)
    {
     return 1;
   }
   if(next==n)
    {
      return 0;
    }
    else if(dp[mask]!=-1) 
    {
     return dp[mask];
    }
   else
   {
    lli ret=0;
      for(int i=0;i<n;i++)
       {
          if(arr[next][i]==1 && !(mask &(1<<i)))
           {
              ret+=solve(mask |(1<<i),next+1);
     }
    }
    
    dp[mask]=ret;
    return ret;
   }
 }
int main()
{
 int t;
  cin>>t;
  while(t--)
   {
      maxi=0;
      cin>>n;
      for(int i=0;i<n;i++)
       {
          maxi=maxi | (1<<i);
         for(int j=0;j<n;j++)
          {
             cin>>arr[i][j];
             
       }
    }
    memset(dp,-1,sizeof dp);
    lli ans=solve(0,0);
     cout<<ans<<endl;
   }
}