SPOJ - DETER3：Find The Determinant III (求解行列式)

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 ;

}