Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
||||||||||||
2019-11-24 16:47:46
@nani_99...DCT would make the compile-time <.01 s....very bad question since brute force also give AC |
||||||||||||
2019-11-24 16:43:12
No, you are wrong @anonymous_09.You should use convolution |
||||||||||||
2019-10-11 16:02:19
Declared int instead of long long int, this will cause overflow . and lead to WA :) |
||||||||||||
2019-08-20 16:08:57
sometimes top down is better...(*..*) |
||||||||||||
2019-08-15 16:16:48
TLE then i read comments TLE then i carefully read comments about 1D dp AC :) Last edit: 2019-08-15 16:17:02 |
||||||||||||
2019-05-31 19:51:31
the top down approach gives TLE.... don't know why bottom up - AC Last edit: 2019-05-31 20:29:24 |
||||||||||||
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. |
||||||||||||
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 |
||||||||||||
2019-03-16 19:26:42
Top-down DP works. Finally got AC after many TLEs. Hint: 1D memoization works. |
||||||||||||
2018-10-11 13:41:50
Learn Bitmask DP first.. Use mask to keep track which books have been taken so far. |