ASSIGN - Assignments


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


hide comments
grextrex: 2017-10-12 07:41:22

solved in one go... easy peasy

rohit1507: 2017-10-06 23:04:36

Just Wow! Test cases can be improved!

beginner5022: 2017-09-28 13:43:48

Last edit: 2017-09-28 14:34:42
vishesh197: 2017-09-23 08:41:59

first google what is bitmask and then solve the question.Logic is same involving recursion and dp but it has to be implemented with bitsmask to reduce time to O(n*2^n).

nessaa_05: 2017-07-23 12:16:27

can anyone please explain the question

namitp: 2017-07-07 22:23:55

Nice Question.....
Learnt a lot....

sharif ullah: 2017-06-15 20:22:52

Need Hints???
follow these step->
step-1: First try to solve this problem using all possible option ,recursion;
step-2: draw the tree in paper,for 1st test case,
step-3:Observe there will happen overlapping,so DP!!!
step-4:Now!! what is state?? at frist there may be 2 sate dp(student no,bitmask/track which topics u choose till now);
step-5: Now!! again see at tree diagram #student =no of 1 in bitmask;
step-6:So state will only bitmask;
step-7:WA answer??
step-8:Use long long .

Last edit: 2017-06-15 20:25:08
da_201501181: 2017-06-09 07:16:07

Worth solving to learn something new in world of DP..!!

leafbebop: 2017-06-07 09:00:33

I made a heavy test with 80*20*all-one on my laptop, it was 2.921 seconds but I got AC with 0.92 seconds.

akash619j: 2017-05-30 11:30:37

Declared int instead of long long int costed me 1 WA!


Added by:gawry
Date:2005-10-08
Time limit:2.997s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET