UVa 684 - Integral Determinant

#数学 #高斯消元 #行列式

Published on 2016-03-15

描述

给定一个 $n(1\le n \le 30)$ 阶行列式，请你求行列式的值。

样例输入

样例输出

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}$ 。

算法：思路很清晰，不断的把行列式降维度。
假设为 $n$ 阶行列式，先进行列对换，使第一个元素为第一行中最大的元素（为了精度），如果全为 0，那么行列式的值直接就是 0。否则根据减一行的任意倍，值不改变的定理，让第一行除了第一个全为 0，把行列式的值化为 $D = a_{i, j}A_{i, j}$ 。接着迭代下去即可。

注意到题目说明输出是整数，而且要求使用分数来避免精度问题。我懒得写分数类，直接送上 __float128 128位的浮点数来避免精度，就是时间有点慢。

代码

//  Created by Sengxian on 3/15/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  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)
                a[i][j] = ReadInt();
        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
*

QTREE 1 - Query on a tree I UVa 472 - Simultaneous Equations

Sengxian's Blog

UVa 684 - Integral Determinant

描述

样例输入

样例输出

分析

代码

附加输入

附加输出