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


hide comments
akshayvenkat: 2017-05-09 02:58:21

Explanation of first test case :

Sx denotes Student X , Tx denotes topic Y

Way 1 : S1 T1 , S2 T2 , S3 T3
Way 2 : S1 T1 , S2 T3 , S3 T2
Way 3 : S1 T2 , S2 T1 , S3 T3
Way 4 : S1 T2 , S2 T3 , S3 T1
Way 5 : S1 T3 , S2 T1 , S3 T2
Way 6 : S1 T3 , S2 T2 , S3 T1

(i.e., in Way 5 , Student 1 is assigned topic 3 , Student 2 is assigned topic 1 , and Student 3 is assigned topic 2)

Note that for the following input :

3
1 0 0
1 0 0
1 0 0

The output is 0. Since student 1 can only take topic 1 , he takes that, and no other student can choose any topic, since they either dont like it (or) their preferred topic(s) has been already chosen by some other student.

A great DP+Bitmask problem for beginners.

Khairo21: 2017-04-03 23:06:45

using printf("%I6d") get WA -_-
but AC in cout :D

deadpool_18: 2017-03-29 10:10:34

explain the test case please!

Last edit: 2017-03-29 13:24:03
kshubham02: 2017-03-24 14:00:59

O(2^N * N) solution by clearing complete DP array every time ===> TLE
O(2^N * N) solution by clearing DP array only upto n and (1<<n) every time ===> AC 2.00
Can't seem to understand which approach runs in smaller time :/

cake_is_a_lie: 2017-02-24 03:30:41

Wow, AC and #2 time on 1st try :-D
Bit operations galore and O(2^N * N), as opposed to O(2^N * N^2).
A bit of combinatorics and common sense help a lot in making that solution faster; so does __builtin_popcount.

Last edit: 2017-02-24 03:35:22
chapaniyash: 2017-02-02 23:26:11

to count no of 1s in mask use __builtin_popcount(mask);

practice9535: 2017-01-18 06:33:35

how people are solving it in 0.15 sec... mine solution dp(top down) took 2.5 secs.... is there any better and optimal method to solve??????/

saurav786: 2016-11-07 21:31:07

Topdown+bitmasking :-D

poomrokc: 2016-10-15 08:20:36

My O(2^n*n) Gets tle Xp for each case lol

dev: 2016-10-10 16:49:52

Very Nice DP + BitMasking !
O(2^n * n*n ) will give Tle.


Added by:gawry
Date:2005-10-08
Time limit:2.997s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET