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 64bit 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
amitboss:
20180208 16:43:55
my first bitmasking and dp..


excel_blaze:
20180102 09:41:25
AC in 1 go.nice one to try bitmasking 

kspoj:
20171208 10:40:10
my first bitmasking + dp prob :D :D 

grextrex:
20171012 07:41:22
solved in one go... easy peasy 

rohit1507:
20171006 23:04:36
Just Wow! Test cases can be improved! 

beginner5022:
20170928 13:43:48
Last edit: 20170928 14:34:42 

vishesh197:
20170923 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:
20170723 12:16:27
can anyone please explain the question 

namitp:
20170707 22:23:55
Nice Question.....


sharif ullah:
20170615 20:22:52
Need Hints???

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