#BANDMATR. Determinant of Banded Matrices
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:
http://sepwww.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 guarantteed 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