ASSIGN - Assignments

no tags 

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


Added by:gawry
Date:2005-10-08
Time limit:2.997s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 VB.net

hide comments
xxbloodysantaxx: 2015-07-16 14:31:27

Took my 8 hours !!
I was able to figure out the solution with complexity O(N^2 * 2^N ) but to achieve O(N*2^N) , I dont know dont waste much time on it just see it :P

sai krishna: 2015-05-29 15:57:07

Any one please explain this test case,unable to understand
1
5
1 1 0 1 0
0 0 1 0 1
1 1 1 0 0
0 0 1 0 1
1 1 1 0 1

Siddharth: 2015-02-28 16:01:13

Same algorithm in JAVA gives TLE... :( Wasted a hell lot of time...

venu gangireddy: 2015-02-27 06:41:01

awesome problem....

Last edit: 2015-02-27 06:41:39
californiagurl: 2015-02-05 12:15:56

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

ALISHA: 2015-01-29 07:45:49

there is nothing wrong with memoization.
code indeed gets accepted!! time 2.27 sec :P :P

CoNtRaDiCtIoN: 2015-01-22 08:56:42

great problem learnt a lot

Archit Jain: 2014-08-16 09:27:00

enjoyed solving it
There is no test case in which a student dislikes all the subjects

Mudit Jain: 2010-04-30 12:57:25

if a student likes no subject? that means if all preferences are 0's then?