P7112 【模板】行列式求值 题解(高斯消元+辗转相除)

题目链接

题目思路

先介绍行列式的变化对于行列式值的改变

1 如果交换矩阵的两行，则行列式的符号要取反

2 如果用某数t乘以矩阵的一行，则行列式等于原行列式的t倍

3 三角阵的行列式等于对角线元素乘积

4 从矩阵的行k减去行i的l倍，行列式不会改变，即消元过程不改变行列式

根据上面的式子用高斯消元化简即可

注意这里不需要求逆元，由于行列的相互加减不会影响行列式的值

所以使用辗转相除法

代码

#include
#define fi first
#define se second
#define debug cout<<"I AM HERE"<a[j][i]){
                swap(a[i],a[j]);
                flag^=1;
            }
            while(a[j][i]){
                swap(a[i],a[j]);
                flag^=1;
                ll p=a[j][i]/a[i][i];
                for(int k=i;k<=n;k++){
                    a[j][k]=(a[j][k]+(mod-p)*a[i][k])%mod;
                }
            }
        }
        ans=ans*a[i][i]%mod;
    }
    if(!flag){
        ans=(-ans+mod)%mod;
    }
    return ans;
}
signed main(){
    scanf("%d%d",&n,&mod);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%lld",&a[i][j]);
        }
    }
    ll ans=gs(n);
    printf("%lld\n",ans);
    return 0;
}