Matrix Determinant

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.1s

Java 0.2s

Python 0.2s

Memory limit: 256M

Author:

FatalEagle

Problem type

FatalEagle recently stumbled upon a manga that teaches linear algebra. A particularly interesting topic was matrix determinants. Your task is simple: given $A$ ~A~, an $N \times N$ ~N \times N~ matrix, find its determinant! Since this number can be really big, we want to find its value $\bmod 1\,000\,000\,007$ ~\bmod 1\,000\,000\,007~ $(10^9+7)$ ~(10^9+7)~.

Input Specification

The first line of input will have $N$ ~N~.

The next $N$ ~N~ lines will have $N$ ~N~ integers each. The $j^{th}$ ~j^{th}~ integer of the $i^{th}$ ~i^{th}~ line will contain $A_{i,j}$ ~A_{i,j}~ $(-10^9 \le A_{i,j} \le 10^9)$ ~(-10^9 \le A_{i,j} \le 10^9)~.

For cases worth 30% of the total marks, $1 \le N \le 8$ ~1 \le N \le 8~.

For cases worth another 30% of the total marks, $1 \le N \le 20$ ~1 \le N \le 20~.

For all test cases, $1 \le N \le 500$ ~1 \le N \le 500~.

Output Specification

The output should be a single integer in the range $[0, 1\,000\,000\,007)$ ~[0, 1\,000\,000\,007)~, the determinant of the matrix $A$ ~A~.

Sample Input 1

2
-1 3
-5 7

Sample Output 1

Sample Input 2

6
1 3 5 2 4 6
2 5 4 3 1 6
6 1 2 3 4 5
2 5 1 3 6 4
4 5 1 2 3 6
5 4 3 6 1 2

Sample Output 2

Comments

3

Plasmatic commented on July 5, 2021, 5:34 a.m.

If you would like to test your determinant code but are getting TLE on this problem here is an alternative (on another judge) that has a 5 second TL if you want to see it run on some larger cases.

-33

harry7557558 commented on April 19, 2020, 12:43 a.m. ← edit 250 →

(removed comment)

This comment is hidden due to too much negative feedback. Show it anyway.

23

ManchurioX commented on April 20, 2020, 4:02 a.m. ← edited →

Hey! Spamming the "view previous" button on the comment above (the one with many edits) will get you captcha'd so be warned!!!

9
Moana commented on April 19, 2020, 11:06 p.m. ← edit 8 →
Comment by harry7557558: original edit 2 edit 6 edit 12 edit 13+; Account kicked out for spam requesting and is currently inaccessible.

Python hard-coding AC submission; First proper Python AC solution; PyPy 2 AC'd with 0.2s TL;

Some facts related to the comment with many edits:

harry7557558 was my primary account; After losing that account for being stupid, this account becomes my primary account;

I use to downvote this comment using 5 a cc ou n ts; The vote dropped from -2 to -6 after this edit and I voted it to 0 after the current edit;

DMOJ prevents me from merging Harry7557558_wcipeg to harry7557558; I'm trying to delete that account and that comment, if someone could help me I'd appreciate :)

Edited Oct.13, 2020. $\mathsf{\color{#FFFFFF00}{\text{Downvote or upvote you decide.}}}$

$\mathsf{\tiny{\color{#80808080}{\text{If you think these comments are polluting the comment area, don't hesitate to delete them. @admins}}}}$

11

FatalEagle commented on Jan. 20, 2015, 8:32 p.m.

There are a large number of test cases with increasing size. This problem is to test the efficiency of your matrix determinant algorithm -- in other words, the constant matters in this question!

0

bobhob314 commented on Jan. 26, 2015, 7:25 p.m. ← edited →

Wait Fatal so you mean e.g. for $T(n) = \mathcal{O}(f(n))$ ~T(n) = \mathcal{O}(f(n))~, if $f(n)$ ~f(n)~ were to be $2n^3$ ~2n^3~ or something, then the $2$ ~2~ coefficient would matter?

0

bobhob314 commented on Jan. 26, 2015, 7:25 p.m.

Or sorry, I goofed. What do you mean by constant?