SP4533 BANDMATR - Determinant of Banded Matrices

计算矩阵行列式使用高斯消元法的时间复杂度为 $O(n^3)$，而对于三对角矩阵，可以通过递推方法在 $O(n)$ 的时间内完成。在这个问题中，你需要计算带状矩阵的行列式。带状矩阵是一种稀疏矩阵，其非零元素集中在主对角线及其两侧若干条次对角线所构成的一个带状区域内。我们给定一个 **N×N** 的整数带状矩阵，该矩阵在主对角线两侧各有 **M** 条次对角线，要求你计算此矩阵的行列式。例如，三对角矩阵在主对角线两侧各有 1 条次对角线，而样例输入中的 8×8 矩阵则在每侧有 2 条。若想了解更多带状矩阵的相关内容，可参阅 Thorson 的论文： http://sepwww.stanford.edu/oldreports/sep20/20\_11\_abs.html

输入数据最多有 10 组。对于每组输入： 首先是一行包含矩阵的维度 **N (1 < N < 501)**，接着是 **N** 行，各行有 **N** 个整数，数值范围在 -10001 和 10001 之间。保证主对角线两侧的次对角线条数 **M < 51**，即整个带状区域至多有 101 条对角线（包括主对角线）。请使用 `scanf` 进行输入输出，避免使用 STL 的输入输出方法。

对于每个输入矩阵，输出其行列式对 $10^9 + 7$ 取模后的结果。 提示：可以使用 Montgomery 乘法来优化计算速度，详见以下链接： http://everything2.com/title/Montgomery%2520multiplication **本翻译由 AI 自动生成**