P7112 【模板】行列式求值

核心是化为下三角型矩阵，然后对角线元素相乘，注意里面要使用辗转相除法，因为不保证 $p$ 是一个质数。

#include <bits/stdc++.h>
#define MAXN 605
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int a[MAXN][MAXN];
int n,p;
struct Matrix{
	int n,m;
	int a[3][3];
	void init(){
		memset(a,0,sizeof(a));
		for (int i=1;i<=n;++i) a[i][i]=1;
	}
	void reverse(){
		a[1][1]=0,a[2][2]=0;
		a[1][2]=1,a[2][1]=1;
	}
};
Matrix operator*(Matrix A,Matrix B){
	Matrix C;
	C.n=A.n,C.m=B.m;
	for (int i=1;i<=C.n;++i){
		for (int j=1;j<=C.m;++j){
			C.a[i][j]=0;
			for (int k=1;k<=A.m;++k){
				C.a[i][j]=(C.a[i][j]+1LL*A.a[i][k]*B.a[k][j]%p)%p;
			}
		}
	}
	return C;
}
namespace Gauss{
	int Determinant(){
		int sign=1;
		for (int i=1;i<=n;++i){//将第i行看成主元
			for (int j=i+1;j<=n;++j){
				Matrix op;
				op.n=op.m=2;
				op.init();
				//相当于给 i,j 行的对应元素组成的列向量乘一个 2x2 的矩阵
				while (a[i][i]){
					int t=a[j][i]/a[i][i];
					a[j][i]=(a[j][i]-1LL*a[i][i]*t%p+p)%p;

					swap(a[i][i],a[j][i]);

					Matrix s;
					s.n=s.m=2;
					s.a[1][1]=0,s.a[1][2]=1;
					s.a[2][1]=1,s.a[2][2]=-t;

					op=op*s;
					sign=-sign;
				}
				swap(a[i][i],a[j][i]);
				sign=-sign;
				Matrix rev;
				rev.n=rev.m=2;
				rev.reverse();
				op=op*rev;
				for (int k=i+1;k<=n;++k){
					int aik=a[i][k],ajk=a[j][k];
					a[j][k]=(1LL*op.a[1][1]*ajk%p+1LL*op.a[2][1]*aik%p)%p;
					a[i][k]=(1LL*op.a[1][2]*ajk%p+1LL*op.a[2][2]*aik%p)%p;
				}
			}
		}
		int ans=1;
		for (int i=1;i<=n;++i){
			ans=ans*a[i][i]%p;
		}
		return ((ans*sign+p)%p+p)%p;
	}
};
using namespace Gauss;
int main(){
	// freopen("P7112_1.in","r",stdin);
	n=read(),p=read();
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			a[i][j]=read();
		}
	}
	printf("%d",Determinant());
}

不知道为什么 T 了，不想卡常了。