行列式det(A)
Background
行 列式在中，是一函，其定域n × n的矩A，取值一量，作det(A)或|A|。行列式可以看做是有向面或的概念在一般的里得空中的推。或者，在 n 里得空中，行列式描述的是一性「」所造成的影。是在性代、多式理，是在微分中（比如元分法中），行列式 作基本的工具，都有著重要的用。
行列式概念最早出在解性方程的程中。十七世晚期，孝和布尼茨的著作中已使用行 列式定性方程解的以及形式。十八世始，行列式始作立的概念被研究。十九世以後，行列式理一步得到展和完善。矩概念的 引入使得更多有行列式的性被，行列式在多域都逐出重要的意和作用，出了性自同和向量的行列式的定。
行列式的特性可以被概括一多次交替性形式，本使得行列式在里德空中可以成描述「」的函。
by Wiki
The Problem
定一 N 矩，算出其行列式值。 入明 ：
出明 ：
det(A) 可能很大，出 mod 100000007 的答案即可。
例入 ：
2 3 4 1 2 3 -9 -18 -27 0 -5 -7 6 -1 3
例出 ：
提示 ：
出 ：
先素做法 : 降 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
「」
自 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(!mi[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;
}
文章定位：
