SPOJ Problem Set (classical)

2832. Find The Determinant III

Problem code: DETER3

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.

Example

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

Output:
0
0
2

算矩阵对应行列式的值,

/*************************************************************************
    > File Name: st9.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年01月29日 星期四 18时58分56秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

const int N = 300;

LL mat[N][N];

LL Det (int n, int mod)
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			mat[i][j] %= mod;
		}
	}
	LL res = 1;
	for (int i = 0; i < n; ++i)
	{
		if (!mat[i][i])
		{
			bool flag = false;
			for (int j = i + 1; j < n; ++j)
			{
				if (mat[j][i])
				{
					flag = true;
					for (int k = i; k < n; ++k)
					{
						swap (mat[i][k], mat[j][k]);
					}
					res = -res;
					break;
				}
			}
			if (!flag)
			{
				return 0;
			}
		}
		for (int j = i + 1; j < n; ++j)
		{
			while (mat[j][i])
			{
				LL t = mat[i][i] / mat[j][i];
				for (int k = i; k < n; ++k)
				{
					mat[i][k] = (mat[i][k] - t * mat[j][k]) % mod;
					swap (mat[i][k], mat[j][k]);
				}
				res = -res;
			}
		}
		res = (res * mat[i][i]) % mod;
	}
	return (res + mod) % mod;
}

int main()
{
	int n;
	LL p;
	while (~scanf("%d%lld", &n, &p))
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				scanf("%lld", &mat[i][j]);
			}
		}
		LL ans = Det (n, p);
		printf("%lld\n", ans);
	}
	return 0;
}