## UVa 684 - Integral Determinant

Published on 2016-03-15

## 样例输入

2
5 2
3 4
3
2 3 5
1 6 7
4 8 9
0


## 样例输出

14
-27
*


## 分析

$k_1k_2k_3..k_n$ 为 1 ~ n 的一个排列，记 $\pi(k_1k_2k_3..k_n)$ 为排列 $k$ 的逆序对数量。

• $n$ 阶行列式的值：若 $s$ 为 1 ~ n 的所有排列组成的集合，行列式 $i$$j$ 列的元素为 $a_{i, j}$，则行列式的值为 $\sum_{k \in s}(-1)^{\pi(k_1k_2k_3..k_n)}a_{1, k_1}\cdot a_{2, k_2}\cdot ...\cdot a_{n, k_n}$
• 交换行列式的任意行（列），行列式的值符号改变。
• 行列式的某一行（列）全部减去行列式的另一行（列）的任意倍，行列式的值不改变。
• 若行列式的某一行（列）全为 0，那么行列式的值为 0。
• 代数余子式：在一个 $n$ 阶行列式 $D$ 中,把元素 $a_{i,j} (i,j=1,2,.....n)$ 所在的行与列划去后，剩下的 $(n-1)^2$ 个元素按照原来的次序组成的一个 $n-1$ 阶行列式 $M_{i,j}$，称为元素 $a_{i, j}$ 的余子式，$M_{i, j}$ 带上符号 $(-1)^{(i+j)}$ 称为 $a_{i, j}$ 的代数余子式，记作 $A_{i, j} = (-1)^{(i+j)}M_{i, j}$
• 若行列式的某一行（列）仅有一个数不为 0，为 $a_{i, j}$ 那么行列式的值为 $a_{i, j}$ 乘其代数余子式，记作 $D = a_{i, j}A_{i, j}$

## 代码

//  Created by Sengxian on 3/15/16.
//  UVa 684 行列式求值
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

inline int ReadInt() {
int n = 0, ch = getchar(); bool flag = false;
while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
while (isdigit(ch)) n = (n << 1) + (n << 3) + ch - '0', ch = getchar();
return flag ? -n : n;
}
typedef long long ll;
typedef __float128 type;
const type eps = 1e-8;
const int maxn = 30 + 3;
int n;
type a[maxn][maxn];

type myAbs(type a) {
return a > 0 ? a : -a;
}

type solve() {
double product = 1.0;
bool flag = true;
for (int i = 0; i < n; ++i) {
int idx = i;
for (int j = i; j < n; ++j)
if(myAbs(a[i][j]) > myAbs(a[i][idx])) idx = j;
if (myAbs(a[i][idx]) < eps) return 0; //一行全为 0
if (idx != i) {
flag = !flag;
for (int j = i; j < n; ++j) swap(a[j][idx], a[j][i]);
}
for(int j = i + 1; j < n; ++j)
for(int k = n - 1; k >= i; --k)
a[k][j] -= a[k][i] / a[i][i] * a[i][j];
product *= a[i][i];
}
return flag ? product : -product;
}

int main() {
while (n = ReadInt(), n) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
printf("%lld\n", (ll)solve());
}
puts("*");
return 0;
}



## 附加输入

30
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 3 4 2 1 2 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 9 5 4 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 2 0 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 5 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 3 0 1 0 0 0 7 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 7 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 5 1 2 9 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 7 4 1
0


## 附加输出

-1725324300
*