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
hello_world123:
20180415 08:36:45
Why is time complexity O(n*2^n) and not O(n*n*2^n) ? 

Aditya Kumar:
20180412 20:54:51
bitmasking is cool!! 

sinersnvrsleep:
20180318 11:40:47
use long long int costed me a wrong answer 

kkrishnaai:
20180226 08:29:59
My 50th :) 

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 
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 