P7112 【模板】行列式求值 题解

· · 题解

学《高等代数》第二章的时候过来搜了搜模板，结果真搜到了。于是来水一篇题解。

本文部分内容来自《高等代数》。

可能更好的阅读体验

行列式定义

对于一个 n 阶行列式

\begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix}

其结果为所有不同行不同列的元素乘积的代数和。用数学语言写为：

\sum_{j_1j_2 \cdots j_n} (-1) ^ {\tau(j_1j_2\cdots j_n)} a_{1j_1}a_{2j_2}\cdots a_{nj_n}

其中 j_1j_2 \cdots j_n 为 1 \sim n 的一个排列。\tau(j_1j_2 \cdots j_n) 表示排列 j 的逆序数的个数。

可以看出，如果 \tau(j_1 \sim j_n) 为偶数，那么该排列对答案的贡献为正。否则为负。

行列式性质

《高代》里原本有七条性质，这里只证明有用的五条。

a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} = \begin{vmatrix} a_{11}& a_{21}& \cdots & a_{n1} \\ a_{12}& a_{22}& \cdots & a_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n}& a_{2n}& \cdots & a_{nn} \end{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ ka_{i1} & ka_{i2} & \cdots & ka_{in}\\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} = k \begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{i1} & a_{i2} & \cdots & a_{in}\\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix}

证明：

首先考虑 n 级行列式的 n! 项。如果把他们分成 n 组，一定有一种方案，使得第 1 组中都含有 a_{i1}，第 2 组中都含有 a_{i2}，以此类推。如果第 j 项提出 a_{ij} 后记作 A_{ij}，那么有

a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{vmatrix} a_{i1}A_{i1} + a_{i2}A_{i2} + \cdots + a_{in}A_{in} = \sum_{j = 1}^{n} a_{ij}A_{ij}

这将方便我们后面的讨论。

现在证明性质二：

a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & & \vdots \\ ka_{i1} & ka_{i2} & \cdots & ka_{in}\\ a_{n1}& a_{n2} & \cdots & a_{nn} \end{vmatrix} ka_{i1}A_{i1} + ka_{i2}A_{i2} + \cdots + ka_{in}A_{in} k(a_{i1}A_{i1} + a_{i2}A_{i2} + \cdots + a_{in}A_{in}) a_{11}& a_{12} & \cdots & a_{1n} \\ a_{21}& a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{i1} & a_{i2} & \cdots & a_{in} \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} \begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ b_1 + c_1 & b_2 + c_2 & \cdots & b_n + c_n \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} = \begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ b_1 & b_2 & \cdots & b_n \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} + \begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ c_1 & c_2 & \cdots & c_n \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix}

证明：

原行列式可写成 (b_1 + c_1)A_{i1} + (b_2 + c_2)A_{i2} + \cdots + (b_n + c_n)A_{in}，这等于右式。

证明太容易而公式又太难打，就不写了。

证明：

\begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{i1} & a_{i2} & \cdots & a_{in} \\ \vdots & \vdots & &\vdots \\ a_{k1} & a_{k2} & \cdots &a_{kn} \\ \vdots & \vdots & &\vdots \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{i1} + a_{k1}& a_{i2} + a_{k2}& \cdots & a_{in} + a_{kn}\\ \vdots & \vdots & &\vdots \\ a_{k1} & a_{k2} & \cdots &a_{kn} \\ \vdots & \vdots & &\vdots \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} = \begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{i1} + a_{k1}& a_{i2} + a_{k2}& \cdots & a_{in} + a_{kn}\\ \vdots & \vdots & &\vdots \\ -a_{i1} & -a_{i2} & \cdots & -a_{in} \\ \vdots & \vdots & &\vdots \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} = \begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{k1} & a_{k2} & \cdots & a_{kn}\\ \vdots & \vdots & &\vdots \\ -a_{i1} & -a_{i2} & \cdots & -a_{in} \\ \vdots & \vdots & &\vdots \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix} = - \begin{vmatrix} a_{11}& a_{12}& \cdots & a_{1n} \\ a_{21}& a_{22}& \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{k1} & a_{k2} & \cdots & a_{kn}\\ \vdots & \vdots & &\vdots \\ a_{i1} & a_{i2} & \cdots & a_{in} \\ \vdots & \vdots & &\vdots \\ a_{n1}& a_{n2}& \cdots & a_{nn} \end{vmatrix}

其中第一步是利用性质四，将第 k 行加到了第 i 行上。

第二步是利用性质四，将第 i 行减去第 k 行。

第三步是利用性质四，将第 i 行加到了第 k 行上。

最后一步是利用性质二，将第 i 行提出 -1。

证毕。

特殊的行列式

  1. 对角行列式

形如

a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{nn} \end{vmatrix}

的行列式称为对角行列式。其结果为 a_{11} \times a_{22} \cdots a_{nn}。

  1. 三角行列式

形如 \begin{vmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ 0 & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ 0 & 0 & 0 & a_{nn} \\ \end{vmatrix} 的行列式被称为三角行列式，其结果与对角行列式相同。

行列式计算

显然，如果按照定义，我们需要 O(n \times n!) 的复杂度。显然无法接受。

由于存在一些特殊的行列式，可以考虑将原行列式转化为三角行列式后求值。思路就是将原行列式利用性质一到四进行转化。

例如有行列式 \begin{vmatrix} 2 & 3 & 5 \\ 3 & 4 & 7 \\ 4 & 3 & 2 \end{vmatrix}，首先可以将 2 \sim 3 行分别加上第一行的 -\dfrac{3}{2}, -2 倍，化为 \begin{vmatrix} 2 & 3 & 5 \\ 0 & -\dfrac{1}{2} & -\dfrac{1}{2} \\ 0 & -3 & -8 \end{vmatrix}。

接下来，把第三行加上第二行的 -6 倍，可得 \begin{vmatrix} 2 & 3 & 5 \\ 0 & -\dfrac{1}{2} & -\dfrac{1}{2} \\ 0 & 0 & -5 \end{vmatrix}。

于是原式化为了一个三角行列式。对角线乘积即为答案 5。

这个方法类似高斯消元的过程。因此就把它叫做高斯消元吧。

可以看出，这个方法的时间复杂度是 O(n ^ 3) 的，完全可以接受。

带模数行列式计算

如果带模数怎么算行列式的值呢？

有一种方法叫做辗转相减法，可以完美的解决这个问题。

比如有行列式 \begin{vmatrix} 3 & 2\\ 4 & 1 \end{vmatrix}，首先先用第二行的第一个数除以第一行第一个数，得到 1。（这里是下取整）。

然后用第二行减去第一行 \times 1，得到 \begin{vmatrix} 3 & 2\\ 1 & -1 \end{vmatrix}。

容易证明第二行第一个数在操作完之后一定小于第一行第一个数。因此交换 1, 2 行，得到 -\begin{vmatrix} 1 & -1\\ 3 & 2 \end{vmatrix}。

重复上述操作，直到第一行为 0。得到这样的行列式：\begin{vmatrix} 0 & 5\\ 1 & -1 \end{vmatrix}。

最后再把一、二行交换即可得到下三角行列式：

1 & -1\\ 0 & 5 \end{vmatrix}

答案即为 -5。

由于在辗转相减的过程中可以取模，所以这个问题就被完美解决了。

分析一下复杂度。易证辗转相减的复杂度与欧几里得算法类似，为 O(\log n) 级别。如果记交换两行复杂度为 O(n)，那么总复杂度就为 O(n ^ 2(\log n + n))。

注意：两行交换时千万别忘变号！！！

代码

#include <algorithm>
#include <cstdio>
#define int long long

using namespace std;

const int N = 610;
int n, p, w[N][N], f;
void Swap(int &a, int &b) {
    for (int i = 1; i <= n; i ++ )
        swap(w[a][i], w[b][i]);
    f ^= 1; // 变号
}
int gauss() {
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ ) {
            while (w[i][i]) {
                int K = (int)w[j][i] / w[i][i];
                for (int k = i; k <= n; k ++ )
                    ((w[j][k] -= K * w[i][k] % p) += p) %= p;
                Swap(i, j);
            } Swap(i, j);
        }
    int ans = 1;
    for (int i = 1; i <= n; i ++ )
        (ans *= w[i][i]) %= p;
    return (f ? (-ans + p) % p : (ans + p) % p);
}

signed main() {
    scanf("%lld%lld", &n, &p);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%lld", &w[i][j]);
    return 0 & printf("%lld\n", gauss());;
}

本文公式很多，可能有笔误。希望大家可以指出。