2012-10-01 20:41:12Morris
[ZJ][逆元、降階、高斯、短碼] a542. 行列式det(A)
行列式det(A)
先來個樸素點做法 : 降階 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;
}
Background
行
列式在數學中，是一個函數，其定義域為n ×
n的矩陣A，取值為一個純量，寫作det(A)或|A|。行列式可以看做是有向面積或體積的概念在一般的歐幾里得空間中的推廣。或者說，在 n
維歐幾里得空間中，行列式描述的是一個線性變換對「體積」所造成的影響。無論是在線性代數、多項式理論，還是在微積分學中（比如說換元積分法中），行列式
作為基本的數學工具，都有著重要的應用。
行列式概念最早出現在解線性方程組的過程中。十七世紀晚期，關孝和與萊布尼茨的著作中已經使用行
列式來確定線性方程組解的個數以及形式。十八世紀開始，行列式開始作為獨立的數學概念被研究。十九世紀以後，行列式理論進一步得到發展和完善。矩陣概念的
引入使得更多有關行列式的性質被發現，行列式在許多領域都逐漸顯現出重要的意義和作用，出現了線性自同態和向量組的行列式的定義。
行列式的特性可以被概括為一個多次交替線性形式，這個本質使得行列式在歐幾里德空間中可以成為描述「體積」的函數。
by Wiki
The Problem
給定一個 N 階矩陣，請算出其行列式值。
輸入說明
：
輸入的每一行包含多筆測試。一個測試資料遞一行包含一個整數 N，1 < N < 11。接下來有 N 行，每行上有 N 個整數
Aij (-100 < Aij < 100) 。
輸出說明
：
det(A) 可能很大，輸出 mod 100000007 的答案即可。
範例輸入 ：
2 3 4 1 2 3 -9 -18 -27 0 -5 -7 6 -1 3
範例輸出 ：
2 144
提示
：
出處
：
行列式
(管理：morris1028)
先來個樸素點做法 : 降階 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
「我非常讚賞這題的取模的數字，因為哪怕你的標準做法沒有用到取
我的做法是的確是高斯消去法，但是除法就暴了。但是我們發現模的
因為，在取模的條件下，可以先把所有矩陣中的數字取模。
剩下的就是求一個數關於一個質數的逆元了，這個子問題你曾經出過
來自 pcsh710742
「
來自 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;
}