BANDMATR - Determinant of Banded Matrices
Computing the determinant of a matrix using Gaussian elimination takes O(n^3). On the other hand, computing the determinant of tridiagonal matrix is O(n) using a recurrence. In this problem you will compute the determinant of banded matrices. A band matrix is a sparse matrix, whose non-zero entries are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side. In this problem, given a banded NxN square integer matrix with M bands on each side of the diagonal, we ask you to compute the determinant of this matrix. For example a tridiagonal matrix has exactly 1 band on each side, and the 8x8 Matrix in the sample input has 2 bands on each side. For a good discussion of banded matrices, see Thorson's paper at: www.stanford.edu/oldreports/sep20/20_11_abs.html
Input
A total of < 10 inputs. For each input,
First line has dimension, N (1 < N < 501), of the matrix, followed by N lines with N integers, each less than 10001, and greater than -10001. It is guaranteed that the number of bands on each side of the diagonal, M < 51. That is there are at most 101 bands in total including the diagonal. Use scanf IO, and avoid stl IO.
Output
For each input matrix, output its determinant modulo 10^9+7.
Hint: Use Montgomery multiplication for fast computation, i.e., see: http://everything2.com/title/Montgomery%2520multiplication
Example
Input: 2 2 0 0 2 2 1 0 0 1 8 1 0 -1 0 0 0 0 0 -1 1 0 -1 0 0 0 0 -1 0 -1 1 -1 0 0 0 0 -1 0 -1 0 -1 0 0 0 0 -1 0 1 0 -1 0 0 0 0 -1 -1 1 0 -1 0 0 0 0 -1 0 -1 1 0 0 0 0 0 -1 0 -1 Output: 4 1 36
hide comments
Min_25:
2015-04-19 13:53:47
Test cases are somewhat weak.
|
|
Chen Xiaohong:
2009-07-01 04:23:08
Changed to 0.5 seconds. Thanks for pointing this out. |
|
Robert Gerbicz:
2009-06-29 11:37:37
Please view topic: https://www.spoj.pl/forum/viewtopic.php?f=3&t=5705 Last edit: 2009-06-29 15:52:11 |
|
[Trichromatic] XilinX:
2009-06-29 08:09:29
Mmm...As I mentioned in other problems, Please set the time limit to 0.5 second or more. If you want to make the time limit tight, please update more test case rather than give a very short time limit. |
|
Chen Xiaohong:
2009-06-29 06:45:19
The SPOJ machine is faster than I thought ... The time limit has been made a little bit tighter to force you to use the "banded property" :-).
|
|
piyifan:
2009-06-28 13:51:22
I use the program of DETER3 got AC.Is this problem special? |
|
Chen Xiaohong:
2009-06-26 18:58:04
Rejudged. |
Added by: | Chen Xiaohong |
Date: | 2009-06-26 |
Time limit: | 0.100s |
Source limit: | 20000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | classical numerical analysis |