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
dmorgans:
20190531 19:51:31
the top down approach gives TLE.... don't know why


saurav_paul:
20190527 14:23:27
First time got TLE after using recursive 2d memorization DP, next I used 1d DP and got accepted, really a very nice problem for learning bitmasking with DP. 

ankityadav:
20190328 12:49:02
NOBODY LOVES THE ASSIGNMENTS


tarungupta:
20190316 19:26:42
Topdown DP works. Finally got AC after many TLEs. Hint: 1D memoization works. 

debsourav33:
20181011 13:41:50
Learn Bitmask DP first.. Use mask to keep track which books have been taken so far. 

elliot1:
20180911 01:31:04
for those who solve the problem and come to show off in comments.. "fuck you" 

souvikd_pro:
20180819 03:56:20
After this, try: https://www.codechef.com/AUG14/problems/TSHIRTS Last edit: 20180819 03:59:23 

be1035016:
20180629 09:50:51
bitset tle:bitmask ac 

s_a_k_s_h_a_m:
20180614 22:22:48
question is quite easy


ankit1cool:
20180611 13:12:12
My first dp+bitmasking learnt a lot 
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 