前置知识

部分内容摘自 OI-Wiki

排列

由 \(1,2,\dots,n\) 组成的有序数组称为 \(1,2,\dots,n\) 的排列。前 \(n\) 个正整数的不同排列有 \(n!\) 个。

如果排列的逆序对个数是奇数，那么这是一个奇排列；如果排列的逆序对个数是偶数，那么这是一个偶排列。

置换

一个有限集合 \(S\) 到自身的双射（即一一对应）称为 的一个置换。集合 \(S=\{a_1,a_2,\dots ,a_n\}\) 上的置换可以表示为

其中 \(p_1,p_2,\dots,p_n\) 是 \(1,2,\dots,n\) 的一个排列。

对换

把 \(1,2,\dots,n\) 的排列中，任意两个不同数 \(i\) 和 \(j\) 交换，得到一个新的排列，这叫做一个对换，用 \((i,j)\) 表示。

性质

• 一个排列一定能通过若干次对换转换成另一个排列。
• 一次对换会改变排列的奇偶性。

矩阵行列式

定义

对于一个矩阵：\(A=\begin{bmatrix}a_{1,1}&\cdots&a_{1,n}\\\vdots &\ddots&\vdots\\ a_{n,1}&\cdots&a_{n,n}\end{bmatrix}\)，定义它的行列式为：

其中，\(p\) 表示 \(1,2,\dots,n\) 的一个排列，\(\pi(p)\) 表示排列的逆序对个数。

性质

部分内容摘自 数学(5)——线性代数：行列式 - 洛谷专栏 (luogu.com.cn)。

转置矩阵行列式不变（1）

矩阵 \(A\) 的转置矩阵为 \(A^T\)，其中 \(A_{i,j}=A^T_{j,i}\)。

原因是排列 \(p_1,p_2,\dots,p_n\) 的奇偶性和 \(p'_1,p'_2,\dots,p'_n\)（满足 \(p'_{p_i}=i\) 的排列） 的奇偶性相同。

交换矩阵的两行（列），行列式取反（2）

原因是对原先枚举的排列 \(p\) 进行一次对换，其奇偶性改变。

对于列的证明，因为转置矩阵行列式不变，所以证明了行的性质也就证明了列的性质。

矩阵一行（列）所有元素同乘一个数，行列式也乘以这个数（3）

表示为 \(\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\\vdots&\vdots&\ddots&\vdots\\ ka_{i,1}&ka_{i,2}&\cdots&ka_{i,n}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,n}\end{bmatrix} = k\times \det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,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{bmatrix}\)。

如果矩阵 \(A\) 中某一行是（列）矩阵 \(B\) 和矩阵 \(C\) 中对应行（列）的所有元素之和，那么 \(\det(A)=\det(B)+\det(C)\)（4）

表示为 \(\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\\vdots&\vdots&\ddots&\vdots\\ b_{i,1}+c_{i,1}&b_{i,2}+c_{i,2}&\cdots&b_{i,n}+c_{i,n}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,n}\end{bmatrix}=\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,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{bmatrix}+\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\\vdots&\vdots&\ddots&\vdots\\ c_{i,1}&c_{i,2}&\cdots&c_{i,n}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,n}\end{bmatrix}\)

如果矩阵中某两行（列）成比例，那么其行列式为 \(0\)（5）

表示为 \(\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\\vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\\vdots&\vdots&\ddots&\vdots\\ ka_{i,1}&ka_{i,2}&\cdots&ka_{i,n}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,n}\end{bmatrix} =0\)

可以这样理解：把上面的第 \(i\) 行所有元素乘 \(k\)，于是得到相同的两行，交换这两行，矩阵不变，行列式不变；但因为交换了两行，所以啊行列式取反，因此行列式为 \(0\)。

矩阵中一行（列）每个元素减去另一行（列）对应元素的若干倍，行列式不变（6）

表示为 \(\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,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{bmatrix}=\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\\vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\\vdots&\vdots&\ddots&\vdots\\ a_{j,1}+ka_{i,1}&a_{j,2}+ka_{i,2}&\cdots&a_{j,n}+ka_{i,n}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,n}\end{bmatrix}\)。

利用性质（4）：\(\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,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{bmatrix}=\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,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{bmatrix}+\det \begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\\vdots&\vdots&\ddots&\vdots\\ a_{i,1}&a_{i,2}&\cdots&a_{i,n}\\\vdots&\vdots&\ddots&\vdots\\ ka_{i,1}&ka_{i,2}&\cdots&ka_{i,n}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,n}\end{bmatrix}\)。

最右边的矩阵第 \(i\) 行和第 \(j\) 行成比例，因此行列式为 \(0\)，由此得证。

上三角矩阵行列式为对角线的乘积（7）

其中上三角矩阵中指的是，只有在 \(i\le j\) 的时候第 \(i\) 行第 \(j\) 列才有值，反之值为 \(0\)。

可以根据行列式的定义理解，只有当所有 \(p_i=i\) 的时候后面的连乘才不是 \(0\)。

同样，对于只有在 \(i\ge j\) 的时候第 \(i\) 行第 \(j\) 列有值的下三角矩阵来说，其行列式也为对角线的乘积。

计算

利用性质（6），可以把矩阵像高斯消元一样转换成上三角矩阵，然后根据性质（7）求值。

当模数为质数的时候可以直接高斯消元：

for(i=1;i<=n;++i) {
    if(!a[i][i]) {
        for(j=i+1;j<=n;++j) if(a[j][i]) { k=i; break; }
        flag^=1,swap(a[i],a[k]);
    }
    Mul(ans,a[i][i]);
    inver=inv(a[i][i]);
    for(j=i+1;j<=n;++j) {
        muler=mul(inver,a[j][i]);
        for(k=i;k<=n;++k)
            Sub(a[j][k],mul(a[i][k],muler));
    }
}
if(flag) Mul(ans,moder-1);

但是当模数不是质数的时候，可能会出现 \(a_{i,i}\) 没有逆元的情况，这个时候就要用类似辗转相除法的方法来消元：

for(i=1;i<=n;++i) {
    if(!a[i][i]) {
        for(j=i+1;j<=n;++j) if(a[j][i]) { k=i; break; }
        flag^=1,swap(a[k],a[i]);
    }
    for(j=i+1;j<=n;++j) {
        if(a[i][i]>a[j][i])
            flag^=1,swap(a[j],a[i]);
        while(a[j][i]) {
            flag^=1,swap(a[j],a[i]);
            muler=moder-a[j][i]/a[i][i];
            for(k=i;k<=n;++k)
                a[j][k]=(a[j][k]+muler*a[i][k])%moder;
        }
    }
    ans=ans*a[i][i]%moder;
}
if(flag) ans=(moder-ans)%moder;