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

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

hide comments
2015-04-19 13:53:47 Min_25
Test cases are somewhat weak.
- My old program didn't change the sign of determinant when swapping rows, but it got AC.

Last edit: 2015-04-19 13:55:12
2009-07-01 04:23:08 Chen Xiaohong
Changed to 0.5 seconds. Thanks for pointing this out.
2009-06-29 11:37:37 Robert Gerbicz
Please view topic: https://www.spoj.pl/forum/viewtopic.php?f=3&t=5705

Last edit: 2009-06-29 15:52:11
2009-06-29 08:09:29 [Trichromatic] XilinX
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.
2009-06-29 06:45:19 Chen Xiaohong
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" :-).
2009-06-28 13:51:22 piyifan
I use the program of DETER3 got AC.Is this problem special?
2009-06-26 18:58:04 Chen Xiaohong
Rejudged.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.