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
m_elbrbry:
20150818 17:56:19
good one :) 

[Mayank Pratap]:
20150805 14:41:28
Took hours to understand the concept of Bitmasks + DP. ..........Coding is easier if u get it... :) 

kejriwal:
20150802 12:46:06
nice problem..!! :) 

xxbloodysantaxx:
20150716 14:31:27
Took my 8 hours !!


sai krishna:
20150529 15:57:07
Any one please explain this test case,unable to understand


Siddharth:
20150228 16:01:13
Same algorithm in JAVA gives TLE... :( Wasted a hell lot of time... 

venu gangireddy:
20150227 06:41:01
awesome problem.... Last edit: 20150227 06:41:39 

californiagurl:
20150205 12:15:56
beautiful optimization! it wasn't obvious to me, although i had a hunch that my original solution will not pass. 

ALISHA:
20150129 07:45:49
there is nothing wrong with memoization.


CoNtRaDiCtIoN:
20150122 08:56:42
great problem 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 