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 >

	rohit1507: 2017-10-06 23:04:36 Just Wow! Test cases can be improved!
	vishesh197: 2017-09-23 08:41:59 first google what is bitmask and then solve the question.Logic is same involving recursion and dp but it has to be implemented with bitsmask to reduce time to O(n*2^n).
	nessaa_05: 2017-07-23 12:16:27 can anyone please explain the question
	namitp: 2017-07-07 22:23:55 Nice Question..... Learnt a lot....
	sharif ullah: 2017-06-15 20:22:52 Need Hints??? follow these step-> step-1: First try to solve this problem using all possible option ,recursion; step-2: draw the tree in paper,for 1st test case, step-3:Observe there will happen overlapping,so DP!!! step-4:Now!! what is state?? at frist there may be 2 sate dp(student no,bitmask/track which topics u choose till now); step-5: Now!! again see at tree diagram #student =no of 1 in bitmask; step-6:So state will only bitmask; step-7:WA answer?? step-8:Use long long . Last edit: 2017-06-15 20:25:08
	da_201501181: 2017-06-09 07:16:07 Worth solving to learn something new in world of DP..!!
	leafbebop: 2017-06-07 09:00:33 I made a heavy test with 8020all-one on my laptop, it was 2.921 seconds but I got AC with 0.92 seconds.
	akash619j: 2017-05-30 11:30:37 Declared int instead of long long int costed me 1 WA!
	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

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