[ZJ] a542 - 行列式 det(A) - http://kuoe0.ch/1852/zj-a542-det-a/

a542-detA.cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

#define mod 100000007

long long int gcd( long long int a, long long int b, long long int &x, long long int &y ) {
	long long int g = a;
	x = 1, y = 0;
	if ( b ) 
		return gcd( b, a % b, y, x ), y -= ( a / b ) * x;
	return g;
}

long long int inverse( int a, int m ) {
	long long int x, y;
	gcd( a, m, x, y );
	return x;
}

int find_not_zero( const int k, const vector< vector< long long > > &m ) {
	for ( int i = k; i < m.size(); ++i ) {
		if ( m[ i ][ k ] )
			return i;
	}
	return -1;
}

int adjust( const long long int x, const int MOD ) {
	return ( x % MOD + MOD ) % MOD;
}

long long int det( vector< vector< long long > > mat ) {
	
	int n = mat.size(), cnt = 0;
	long long ret = 1;

	for ( int i = 0; i < n; ++i ) {

		if ( !mat[ i ][ i ] ) {
			int t = find_not_zero( i, mat );
			if ( t == -1 )
				return 0;
			swap( mat[ i ], mat[ t ] );
			++cnt;
		}

		ret = adjust( ret *= mat[ i ][ i ], mod );

		const int inv = adjust( inverse( mat[ i ][ i ], mod ), mod );
		for ( int j = i + 1; j < n; ++j ) {
			const long long p = adjust( mat[ j ][ i ] * inv, mod );
			for ( int k = 0; k < n; ++k ) {
				mat[ j ][ k ] = adjust( mat[ j ][ k ] -= adjust( p * mat[ i ][ k ], mod ), mod );
			}
		}
	}
	return adjust( ret * ( cnt % 2 ? -1 : 1 ), mod );
}

int main() {
	int n;
	vector< vector< long long > > mat;

	while ( ~scanf( "%d", &n ) ) {
		mat = vector< vector< long long > >( n, vector< long long >( n ) );


		int x;
		for ( int i = 0; i < n; ++i ) {
			for ( int j = 0; j < n; ++j ) {
				scanf( "%d", &x );
				mat[ i ][ j ] = adjust( x, mod );
			}
		}

		printf( "%lld\n", det( mat ) );
	}
	return 0;
}