| layout | title | date | tags | ||
|---|---|---|---|---|---|
post |
[ZJ] a542 - 行列式 det(A) |
2012-10-03 |
|
題目網址：a542: 行列式det(A)
題目很單純，給定一個 N × N 的矩陣，求其 determinant 即可！
- 矩陣大小 N，2 ≤ N ≤ 600
- 第 i 列第 j 行的矩陣元素 Ai,j，-100 ≤ Ai,j ≤ 100
對於每一筆測試資料，其第一行由一整數 N 開始，表示矩陣大小。接下來會有 N 列，每列有 N 個整數，即為矩陣元素。
對於每一筆測試資料，輸出該矩陣之 determinant 值。由於數值可能過大，需要將輸出以 100000007 取模數！
求矩陣 determinant 算是滿經典的題目之一，一般利用高斯消去法即可。
首先從第 i (1 ≤ i ≤ N) 列開始，查看第 i 列的第 i 個元素是否為 0，若等於 0，找出第 i 個元素不等於 0 的第 j (i ≤ j ≤ N) 列，並與當前列交換。若找不到表示 determinant 為 0，直接回傳 0 即可。
目前就使得第 i 列的第 i 個元素不為 0，對於第 j (i ≤ j ≤ N) 列，我們將第 i 列乘以 (-Aj,i / Ai,i) 加到第 j 列，該步驟可使得第 j （i ≤ j ≤ N）列中的第 i 個元素皆為 0。
如此重複上述步驟至第 N 列，將會得到一個上三角矩陣（主對角線下方元素皆為 0）。其主對角線乘積即為 determinant！最後再將答案以 100000007 取模數即為答案！
可是（人生就是這麼多的可是），答案是錯的。
這題目看似容易，實際卻也沒這麼容易，除了基本的高斯消去法外，另外還暗藏著模反元素的觀念！而陷阱並不在題目的敘述中，而是在輸出的規範！輸出提到了為了避免數字過大，答案需要以 100000007 取模數！
根據同餘定理，模數運算中仍擁有加法 (+)、減法 (-)、乘法 (×)此三種運算，而除法 (÷) 將不被模數運算所支援！因此，回顧一下上述的高斯消去法，可以發現在進行消去時，我們用到了除法 (-Aj,i / Ai,i)。如此一來，該 determinant 答案固然是錯誤的。另外，由於題目給定的皆為整數，determinant 的結果也必為整數，但是既然使用了除法，答案可能會因為浮點數的精準度關係而產生些微的誤差！
既然上面的高斯消去法不能使用了，那麼該如何解該題目呢？或許會想改用降階法去解決，我相信應該是可行的，不過程式的 overhead 會較大，且時間複雜度也較高！於是，我們還是使用高斯消去法來解決，不過是修改過的高斯消去法！
除法運算中，x 的反元素（inverse）定義為 x-1 = 1/x（P.S. 任何數與其反元素相乘為 1）。所以修改前的高斯消去法中，有一段將第 i 列乘上 (-Aj,i / Ai,i)，可以將其看成 (-Aj,i × (Ai,i)-1)。
接著只要將該 (Ai,i)-1 以模反元素（任一數與其模反元素相乘取模數等於 1）帶入，高斯消去法即可繼續運作了！
這題是 Morris 前輩自己出題，並在前幾天問我的題目。不過想了很久，沒啥頭緒。最後還是 morris 前輩向他人詢問後，看到反元素這關鍵字才想出解法！
<script src="https://gist.github.com/KuoE0/3822760.js"></script>Time Complexity: O(N3)
Source code on gist.