行列式求值

推荐了解：

矩阵求逆

高斯消元

行列式求值

P7112 【模板】行列式求值

对于一个 $n$ 阶的方阵 $A$，它的 $|A|$ 是行列式 $|A|$ 的值。

通过后面说的运算方式和求值的方式，我们将矩阵消成上三角形式然后求值。交换行的时候注意正负号，计算的时候注意精度。

行列式基本运算

• 加法（减法）：

$$\begin{gathered} \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &b_{i,1}+a_{i,1}&b_{i,2}+a_{i,2}&\cdots&b_{i,n}+a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} = \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &b_{i,1}&b_{i,2}&\cdots&b_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} + \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{i,1}&a_{i,2}&\cdots&a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} \end{gathered}$$

• 乘法：

$$\begin{gathered} \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &k\times a_{i,1}&k\times a_{i,2}&\cdots&k\times a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} = k\times \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{i,1}&a_{i,2}&\cdots&a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} \end{gathered}$$

• 一行加上另外一行的倍数：

$$\begin{gathered} \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &k\times a_{1,1}+a_{i,1}&k\times a_{1,2}+a_{i,2}&\cdots&k\times a_{1,n}+a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} = \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{i,1}&a_{i,2}&\cdots&a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} \end{gathered}$$

• 交换行：

$$\begin{gathered} \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{i,1}&a_{i,2}&\cdots&a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{j,1}&a_{j,2}&\cdots&a_{j,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} = - \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &a_{2,1}&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{j,1}&a_{j,2}&\cdots&a_{j,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{i,1}&a_{i,2}&\cdots&a_{i,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} \end{gathered}$$

求值公式

• 对角

$$\begin{gathered} \begin{vmatrix} &a_{1,1}&0&\cdots&0&\\ &0&a_{2,2}&\cdots&0&\\ &\vdots&\vdots&\ddots&\vdots&\\ &0&0&\cdots&a_{n,n}&\\ \end{vmatrix} =a_{1,1}\times a_{2,2}\times \cdots\times a_{n,n} \end{gathered}$$

• 上三角（可以“无伤”消掉多余部分）

$$\begin{gathered} \begin{vmatrix} &a_{1,1}&a_{1,2}&\cdots&a_{1,n}&\\ &0&a_{2,2}&\cdots&a_{2,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &0&0&\cdots&a_{n,n}&\\ \end{vmatrix} =a_{1,1}\times a_{2,2}\times \cdots\times a_{n,n} \end{gathered}$$

• 下三角（可以“无伤”消掉多余部分）

$$\begin{gathered} \begin{vmatrix} &a_{1,1}&0&\cdots&0&\\ &a_{2,1}&a_{2,2}&\cdots&0&\\ &\vdots&\vdots&\ddots&\vdots&\\ &a_{n,1}&a_{n,2}&\cdots&a_{n,n}&\\ \end{vmatrix} =a_{1,1}\times a_{2,2}\times \cdots\times a_{n,n} \end{gathered}$$

• 副对角

$$\begin{gathered} \begin{vmatrix} &0&0&\cdots&a_{1,n}&\\ &\vdots&\vdots&\ddots&\vdots&\\ &0&a_{n-1,2}&\cdots&0&\\ &a_{n,1}&0&\cdots&0&\\ \end{vmatrix} =(-1)^{\frac{n(n-1)}{2}}a_{1,n}\times \cdots \times a_{n-1,2}\times a_{n,1} \end{gathered}$$

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar();
  }
  return k*f;
} 
const int o_o=610;
int n,a_a[o_o][o_o],m_d;
int f_i(){
  int a_s=1,f_h=1;
  for(int i=1;i<=n;i++){//枚举行 
    for(int j=i+1;j<=n;j++){//枚举每回处理的行 
        while(a_a[i][i]){
            int d_i=a_a[j][i]/a_a[i][i];//消项 
            for(int k=i;k<=n;k++)//更新每回处理的行 
                a_a[j][k]=(a_a[j][k]-1ll*d_i*a_a[i][k]%m_d+m_d)%m_d;
            swap(a_a[i],a_a[j]);//交换行 
        f_h=-f_h;//行列式变号 
        } 
        swap(a_a[i],a_a[j]);//交换行 
      f_h=-f_h;//行列式变行 
    }
  }
  for(int i=1;i<=n;i++)a_s=1ll*a_a[i][i]*a_s%m_d;//统计答案 
  a_s=1ll*f_h*a_s;//处理正负 
  return (a_s+m_d)%m_d;//输出 
}
int main(){
  n=r_r();//矩阵大小 
  m_d=r_r();//读入模数 
  
  //读入矩阵 
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)a_a[i][j]=r_r();
  printf("%d\n",f_i());//结果 
  return 0;
}