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
rapiram31: 2022-11-28 05:02:24

Iterate through the bits like we do in fenwick tree with dp it works:)

nayemislamzr: 2022-10-04 04:10:13

dp[20][(1<<20)-1] works

Last edit: 2022-10-04 04:10:36
hv22: 2022-06-05 02:13:37

Cool problem!

thanos_tapras: 2022-01-18 15:58:58

Nice problem.
Dp with bitmasks should do it

arun_code21: 2021-12-15 13:39:45

how (2^n * n) complexity is accepted, time complexity according to this coming in range 10^9?

adam____: 2021-08-27 16:51:29

AC in one, the bitmasks are a really big hint
Used recursive DP, and top down i think

tropo_sphere: 2021-06-26 16:53:19

Can explain O(2^n*n) complexity approach plz! Mine was O(n*n*2^n) with optimization.

null12_21: 2021-06-08 08:11:50

use row...keep a mask to check which index you have been taken i mean which assignment...mask can use with bit operation. use a for loop between the recursive solution. if you on a position on mask dont forget to off it after the iteration

anupam_akib: 2021-05-22 20:14:11

Finally got AC after 1 TLE and 2 WA. Nice problem for beginners who started solving DP with bitmasks.

saurabh_38: 2021-02-18 10:20:22

use-> unsigned long long
Good problem


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