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
dhruvgheewala: 2021-01-30 12:48:33

@brokeboy, my code having similar complexities, but I am getting TLE. Do you have any clue, I am using a 2-d vector and adjacency matrix to store preferences.

Edit: how you got AC with that complexity( Time: O( 2 ^ 20 * n * n * c), 2 ^ 20 * n * n * c = 1M * 20 * 20 * 80 = 1M * 32 * 1000 = 32 * 10 ^ 9)

Last edit: 2021-01-30 12:53:27
ayushpandia: 2021-01-18 14:36:31

Really nice problem

ant_2001: 2021-01-17 13:11:25

I am using DP+bitmask, long long ......test cases give correct answer but I am still getting WA . Please help!

lamda_cdm_10: 2020-10-28 14:29:05

Nice problem for people who are starting to learn bitmasks... has a tight time limit ... enjoyed solving it.

pranavsindura: 2020-09-05 10:50:20

Both top down and bottom up work.

karankamboj: 2020-06-09 15:14:01

AC when used recursive DP
TLE When used bottom up DP
why?

regex0754: 2020-05-18 00:08:22

During Bitmasking,I just left shifted all masks so that I can use 1 indexing.But this gives TLE while normal 0
indexing passes. Is there anything that I am missing while doing 1 indexing ?? If you find something please reply.
Note: I think that Time Complexity should be same.Because ,the number of masks I use are still (2^n).

brokeboy: 2020-05-08 19:55:04

Works with Time = (2^n)*n*n, Space = (2^n)*n, Fast IO

cjchirag7: 2020-05-03 10:20:25

DP with bitmasking with state reduction.
Good problem to learn bitmasking.
Use long long too.
Memoization would also give AC with 1-d DP.

dmorgans: 2020-02-18 19:14:33

my 51st
DP+bitmask, use long long


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