Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

 行列式det(A) 

Background

行 列式在數學中，是一個函數，其定義域為n × n的矩陣A，取值為一個純量，寫作det(A)或|A|。行列式可以看做是有向面積或體積的概念在一般的歐幾里得空間中的推廣。或者說，在 n 維歐幾里得空間中，行列式描述的是一個線性變換對「體積」所造成的影響。無論是在線性代數、多項式理論，還是在微積分學中（比如說換元積分法中），行列式 作為基本的數學工具，都有著重要的應用。

行列式概念最早出現在解線性方程組的過程中。十七世紀晚期，關孝和與萊布尼茨的著作中已經使用行 列式來確定線性方程組解的個數以及形式。十八世紀開始，行列式開始作為獨立的數學概念被研究。十九世紀以後，行列式理論進一步得到發展和完善。矩陣概念的 引入使得更多有關行列式的性質被發現，行列式在許多領域都逐漸顯現出重要的意義和作用，出現了線性自同態和向量組的行列式的定義。

行列式的特性可以被概括為一個多次交替線性形式，這個本質使得行列式在歐幾里德空間中可以成為描述「體積」的函數。

by Wiki

The Problem

給定一個 N 階矩陣，請算出其行列式值。

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

---

先來個樸素點做法 : 降階 O(N!), 沒有用到高斯, 逆元


#include <stdio.h>
#include <algorithm>
#define M(x,i,j) (x.v[i][j])
#define mod 100000007LL
using namespace std;
struct matrix {
    int row, col;
    int v[10][10];
};
matrix x[11];
long long det(int dep) {
    int row, col, i, j, k;
    row = x[dep].row, col = x[dep].row;
    if(row == 2)
        return M(x[dep],0,0)*M(x[dep],1,1) - M(x[dep],0,1)*M(x[dep],1,0);
    long long val = 0;
    for(i = 1; i < row; i++) {
        for(j = 1; j < row; j++) {
            M(x[dep+1],i-1,j-1) = M(x[dep],i,j);
        }
    }
    x[dep+1].row = row-1, x[dep+1].col = col-1;
    for(i = 0; i < row; i++) {
        if(i) {
            for(j = 1; j < row; j++)
                M(x[dep+1],j-1,i-1) = M(x[dep],j,i-1);
        }
        if(M(x[dep], 0, i)) {
            val += ((i&1) ? -1 : 1)*det(dep+1)*M(x[dep],0,i);
            if(val >= mod || val <= mod)
                val %= mod;
        }
    }
    return val;
}
int main() {
    int n, i, j, k;
    while(scanf("%d", &n) == 1) {
        x[0].row = n, x[0].col = n;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &x[0].v[i][j]);
            }
        }
        printf("%lld\n", (det(0)+mod)%mod);
    }
    return 0;
}

---

接下來才是重頭戲, 我先引用幾個人的話

來自 liouzhou_101
「我非常讚賞這題的取模的數字，因為哪怕你的標準做法沒有用到取模數字是質數的特性，但是也給了其他做法一個很寬廣的空間。

我的做法是的確是高斯消去法，但是除法就暴了。但是我們發現模的是質數，我們可以變成乘法，因為除以一個數等於乘上這個數關於取模數的逆元。

因為，在取模的條件下，可以先把所有矩陣中的數字取模。

剩下的就是求一個數關於一個質數的逆元了，這個子問題你曾經出過，放在zerojudge上了。」

來自 pcsh710742
「根據費馬小定理, x^(p-1) ≡ 1 (mod p), 所以當模數是質數的時候，x的模逆元為x^(p-2)」

來自 Chih-Hsuan Kuo
「
假設有個矩陣
   3 7
   5 11
  高斯消去, 要把 5 削去, 所以第二列要減去第一列乘以 5/3, 這個 5/3 是 1/3 乘以第二列的第一個元素, 1/3 在乘法運算中是 3 的 inverse, 但我們現在處於魔術運算, 所以將這個 1/3 替換成 3 在該質數下 inverse 即可, 假設這個 inverse 是 x, 那們第二列就是減去第一列 * x * 5 % mod, 因為 3 * x % mod 會等於 1, 這個特性跟除法運算中的 3 * 1/3 =1 一樣, 前面講的乘法運算應該都要更正成除法運算」

來自 我
「把題目消去成上三角矩陣就行了, 也就是左下角都為 0, 其值是對角線的乘積, 當然要全消也行, 此外當反矩陣不存在時, det(A) 會等於 0, 也就是高斯消去做到一半的時候, 抓到首係數為 0 就可以結束」

以上大神若不願意將對話內容公布的話, 可以要求下架

#include <stdio.h>
#define LL long long
#define mod 100000007LL
LL inverse(LL x, LL p) {
    if(!p)  return 1;
    if(p&1) return x*inverse((x*x)%mod, p>>1)%mod;
    return inverse((x*x)%mod, p>>1);
}
int main() {
    int n, i, j, k;
    while(scanf("%d", &n) == 1) {
        LL mix[15][15] = {}, tmp;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                scanf("%lld", &mix[i][j]);
                mix[i][j] = (mix[i][j]+mod)%mod;
            }
        }
        int inch = 0;
        for(i = 0; i < n; i++) {
            int ch = -1;
            for(j = i; j < n; j++) {
                if(mix[j][i]) {
                    ch = j; break;
                }
            }
            if(ch == -1 || !mix[ch][i]) {
                puts("0");  break;
            }
            if(i != ch) {
                for(j = i; j < n; j++)
                    tmp = mix[i][j], mix[i][j] = mix[ch][j], mix[ch][j] = tmp;
                inch++;
            }
            LL inv, sub;
            for(j = 0; j < n; j++) {
                if(i == j || mix[j][i] == 0)  continue;
                inv = inverse(mix[i][i], mod-2);
                sub = (mix[j][i]*inv)%mod;
                for(k = 0; k < n; k++) {
                    mix[j][k] = mix[j][k] - sub*mix[i][k]%mod;
                    mix[j][k] = (mix[j][k]+mod)%mod;
                }
            }
        }
        if(i != n)  continue;
        LL ans = 1;
        for(i = 0; i < n; i++) {
            ans *= mix[i][i];
            ans %= mod;
        }
        if(inch&1)  ans *= -1;
        printf("%lld\n", (ans+mod)%mod);
    }
    return 0;
}

---

接著為什麼說短碼呢 ? 因為這是我第一次想修成短碼, 多一個函數 sol(), 減少 tab 的使用,
接著就靠 define 去壓縮了

#include <stdio.h>
#define LL long long
#define FOR(i,x,y) for(i=x;i<y;i++)
#define mod 100000007LL
#define SWAP(T,A,B) {T t;t=A,A=B,B=t;}
LL inv(LL x, LL p) {
    if(!p)  return 1;
    if(p&1) return x*inv((x*x)%mod, p/2)%mod;
    return inv((x*x)%mod, p/2);
}
LL mix[15][15], sub, ans;
int n, i, j, k, inch, ch;
LL sol() {
    inch = 0, ans = 1;
    FOR(i,0,n) {
        ch = i;
        FOR(j,i,n)  if(mix[j][i]) {ch = j; break;}
        if(!mix[ch][i]) return 0;
        if(i != ch) {
            FOR(j,i,n)  SWAP(LL,mix[i][j],mix[ch][j]);
            inch++;
        }
        FOR(j,i+1,n) {
            if(!mix[j][i])  continue;
            sub = (mix[j][i]*inv(mix[i][i], mod-2))%mod;
            FOR(k,i,n)
                mix[j][k] = (mix[j][k]-sub*mix[i][k]%mod+mod)%mod;
        }
        ans = (ans*mix[i][i])%mod;
    }
    if(inch&1)  ans *= -1;
    return (ans+mod)%mod;
}
int main() {
    while(scanf("%d", &n) == 1) {
        FOR(i,0,n) {
            FOR(j,0,n) {
                scanf("%lld", &mix[i][j]);
                mix[i][j] = (mix[i][j]+mod)%mod;
            }
        }
        printf("%lld\n", sol());
    }
    return 0;
}