Find The Determinant III

题目链接:https://vjudge.net/problem/SPOJ-DETER3

Description:

Given a NxN matrix A, find the Determinant of A % P.

Input:

Multiple test cases (the size of input file is about 3MB, all numbers in each matrix are generated randomly).

The first line of every test case contains two integers , representing N (0 < N < 201) and P (0 < P < 1,000,000,001). The following N lines each contain N integers, the j-th number in i-th line represents A[i][j] (- 1,000,000,001 < A[i][j] < 1,000,000,001).

Output:

For each test case, print a single line contains the answer.

Sample Input:

1 10
-528261590
2 2
595698392 -398355861
603279964 -232703411
3 4
-840419217 -895520213 -303215897
537496093 181887787 -957451145
-305184545 584351123 -257712188

Sample Output:

0
0
2

题意:

求解行列式模上p的值。

题解:

主要了解下行列式的性质就行了:https://www.cnblogs.com/GerynOhenz/p/4450417.html

之后就类似于高斯消元去计算,代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = ;
int n;
ll p ;
ll b[N][N];
ll Det(int n){
int i,j,k;
ll ret = ;
for(i=;i<=n;i++){
for(j = i+;j <= n;j++){
while(b[j][i]){
ll tmp=b[i][i]/b[j][i];
for(k = i;k <= n;k++)
b[i][k] =((b[i][k] - tmp*b[j][k])%p+p)%p;
swap(b[i],b[j]);
ret = -ret;
}
}
if(!b[i][i]) return ;
ret = ret*b[i][i]%p;
}
if(ret < ) ret = ret+p;
return ret;
}
int main(){
while(scanf("%d%lld",&n,&p)!=EOF){
memset(b,,sizeof(b));
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
cin>>b[i][j];
}
}
cout<<Det(n)<<endl;
}
return ;
}
05-14 05:52