题解：SP2832 DETER3 - Find The Determinant III

· · 题解

三倍经验。

思路

不妨先将行列式看成一个 n 阶方阵

\left|\begin{array}{cc}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots& &\vdots\\a_{n1}&a_{n2}&a_{n3}&\cdots&a_{nn}\end{array}\right|

而行列式经过以下矩阵初等变换不改变其值：

而任意行列式经初等变换都可化为上（下）三角形行列式。

上三角形行列式可以写成如下形式：

\left|\begin{array}{cc}a_{11}&0&0&\cdots&0\\a_{21}&a_{22}&0&\cdots&0\\a_{31}&a_{32}&a_{33}&\cdots&0\\\vdots&\vdots&\vdots& &\vdots\\a_{n1}&a_{n2}&a_{n3}&\cdots&a_{nn}\end{array}\right|

同理，下三角形行列式可以写成如下形式：

\left|\begin{array}{cc}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\0&a_{22}&a_{23}&\cdots&a_{2n}\\0&0&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots& &\vdots\\0&0&0&\cdots&a_{nn}\end{array}\right|

由行列式值的定义

\left|\begin{array}{cc}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots& &\vdots\\a_{n1}&a_{n2}&a_{n3}&\cdots&a_{nn}\end{array}\right|=\sum_{(i_1i_2i_3\cdots i_n)}(-1)^{\tau(j_1j_2j_n)}a_{j1,1}a_{j2,2}a_{j3,3}\cdots a_{jn,n}

易推得上（下）三角形行列式的值为其主对角线元素乘积，即

\left|\begin{array}{cc}a_{11}&0&0&\cdots&0\\a_{21}&a_{22}&0&\cdots&0\\a_{31}&a_{32}&a_{33}&\cdots&0\\\vdots&\vdots&\vdots& &\vdots\\a_{n1}&a_{n2}&a_{n3}&\cdots&a_{nn}\end{array}\right|=\left|\begin{array}{cc}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\0&a_{22}&a_{23}&\cdots&a_{2n}\\0&0&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots& &\vdots\\0&0&0&\cdots&a_{nn}\end{array}\right|=\prod_{i=1}a_{ii}

利用高斯消元将行列式变为上三角行列式后计算即可。

代码

#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define int long long
#define __MULTITEST__
#undef __MULTITEST__
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
int n,mod;
int a[1005][1005]; 
signed main()
{
    #ifdef __MULTITEST__
    signed T;
    scanf("%d",&T);
    while(T--)
    {
    #endif
        while(~scanf("%lld%lld",&n,&mod))
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    scanf("%lld",&a[i][j]);
            int ans=1,f=1;
            for(int i=1;i<=n;i++)
                for(int j=i+1;j<=n;j++)
                {
                    while(a[i][i])
                    {
                        int tmp=a[j][i]/a[i][i];
                        for(int k=i;k<=n;k++)
                            a[j][k]=(a[j][k]-a[i][k]*tmp%mod+mod)%mod;
                        for(int k=1;k<=n;k++)
                            swap(a[i][k],a[j][k]);
                        f=-f;
                    }
                    for(int k=1;k<=n;k++)
                        swap(a[i][k],a[j][k]);
                    f=-f;
                }
            for(int i=1;i<=n;i++)
                ans=ans*a[i][i]%mod;
            printf("%lld\n",(f*ans+mod)%mod);
        }
    #ifdef __MULTITEST__
    }
    #endif
    return 0;
}