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
|
|||||||||||||
2018-04-15 08:36:45
Why is time complexity O(n*2^n) and not O(n*n*2^n) ? |
|||||||||||||
2018-04-12 20:54:51 Aditya Kumar
bitmasking is cool!! |
|||||||||||||
2018-03-18 11:40:47
use long long int costed me a wrong answer |
|||||||||||||
2018-02-26 08:29:59
My 50th :) |
|||||||||||||
2018-02-08 16:43:55
my first bitmasking and dp.. ac in 3 go! Tle_>Tle->Ac! |
|||||||||||||
2018-01-02 09:41:25
AC in 1 go.nice one to try bitmasking |
|||||||||||||
2017-12-08 10:40:10
my first bitmasking + dp prob :D :D |
|||||||||||||
2017-10-12 07:41:22 grextrex
solved in one go... easy peasy |
|||||||||||||
2017-10-06 23:04:36
Just Wow! Test cases can be improved! |
|||||||||||||
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). |