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


da_201501181:
20170609 07:16:07
Worth solving to learn something new in world of DP..!! 

leafbebop:
20170607 09:00:33
I made a heavy test with 80*20*allone on my laptop, it was 2.921 seconds but I got AC with 0.92 seconds. 

akash619j:
20170530 11:30:37
Declared int instead of long long int costed me 1 WA! 

akshayvenkat:
20170509 02:58:21
Explanation of first test case :


Khairo21:
20170403 23:06:45
using printf("%I6d") get WA _

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 