SPOJ.com - Problem ASSIGN

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 Next >

	lovely_bastard: 2025-08-23 00:09:29 Adivce to get the most out of the problem. fisrt solve it rec in O(nn2^) , optim1 the the loop inside the resuive function u can iterate only on the set bits no only the n every loop using popcount or__lg, optim2 the first state is always know the person u assign to the job is always equal the num of set bits in the mask so u can git red of thi state by using popcount comp(n * 2^n). optim3 since u will only traverse in the matrix the set bits ones just store only the only in vector<int> arr[20] it geta big boost boost in the compexity. optim4 solve it using bottom up and get rif of the stack use push dp, pull dp
	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?
	tropo_sphere: 2021-06-26 16:53:19 Can explain O(2^nn) complexity approach plz! Mine was O(nn*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
	saurabh_38: 2021-02-18 10:20:22 use-> unsigned long long Good problem
	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

Submit solution!

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