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
saurav_paul: 2019-05-27 14:23:27

First time got TLE after using recursive 2d memorization DP, next I used 1d DP and got accepted, really a very nice problem for learning bitmasking with DP.

ankityadav: 2019-03-28 12:49:02

NOBODY LOVES THE ASSIGNMENTS
THINK OF 1-D DP
HINT -NO OF PEOPLES HAS ASSIGNED ARE=NO OF SET BITS INT MASK

tarungupta: 2019-03-16 19:26:42

Top-down DP works. Finally got AC after many TLEs. Hint: 1D memoization works.

debsourav33: 2018-10-11 13:41:50

Learn Bitmask DP first.. Use mask to keep track which books have been taken so far.

elliot1: 2018-09-11 01:31:04

for those who solve the problem and come to show off in comments.. "fuck you"

souvikd_pro: 2018-08-19 03:56:20

After this, try: https://www.codechef.com/AUG14/problems/TSHIRTS

Last edit: 2018-08-19 03:59:23
be1035016: 2018-06-29 09:50:51

bitset tle:bitmask ac

s_a_k_s_h_a_m: 2018-06-14 22:22:48

question is quite easy
DP + bitmasking
use long long
for each test case dont clear complete dp table (I got 2 TLE)
10^8 memory can be used

ankit1cool: 2018-06-11 13:12:12

My first dp+bitmasking learnt a lot

horizon121: 2018-05-16 17:12:44

My first dp+bitmasking !! Very nice. Learnt alot


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