All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Sir scolded Rishu
Tag(s):

Bitmask, Dynamic programming, Medium

Problem
Editorial
Analytics

Umesh Sir was busy in assigning tasks to the students in the class, but he gets irritated because of the murmuring sound being caused by some students. And meanwhile, he caught Rishu talking to some other guy. Now, Umesh Sir scolded Rishu and told him that he will make sure that Rishu will get detained by the end of the semester if he will not complete the given task. Although Rishu is too good at algorithms, he was not able to complete the task because he got nervous. Help Rishu otherwise he will get detained.

The task will be: There are n students in the class and Sir chose n topics to give tasks. You have to calculate the number of different ways to assign n different topics to n students such that everybody gets exactly one topic he likes.

Input Format:

The first line of input contains the number of test cases T (1<=T<=80). Each test case begins with the 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 Format:

For each test case output number of different assignments.

SAMPLE INPUT
1
3
1 1 1
1 1 1
1 1 1
SAMPLE OUTPUT
6
Time Limit: 0,5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Уведомления
View All Notifications

?