SPOJ DETER3 (矩阵行列式)

2019-04-14 20:22发布

站内文章 / 模拟电子
17884 0 1401
题意:求矩阵的行列式模p. 这样的情况下就不能用高精度消元搞了,可以在消去的时候用辗转相除避免精度误 差.然后根据行列式的性质,矩阵的元素可以直接模p. 板子题,最终的结果要是正数. #include #include #include #include #include #include using namespace std; #define maxn 333 #define eps 1e-10 long long a[maxn][maxn]; long long n, mod; long long det () //按列化为下三角 { long long res = 1; for(int i = 0; i < n; ++i) { if (!a[i][i]) { bool flag = false; for (int j = i + 1; j < n; ++j) { if (a[j][i]) { flag = true; for (int k = i; k < n; ++k) { swap (a[i][k], a[j][k]); } res = -res; break; } } if (!flag) { return 0; } } for (int j = i + 1; j < n; ++j) { while (a[j][i]) { long long t = a[i][i] / a[j][i]; for (int k = i; k < n; ++k) { a[i][k] = (a[i][k] - t * a[j][k]) % mod; swap (a[i][k], a[j][k]); } res = -res; } } res *= a[i][i]; res %= mod; } return (res+mod)%mod; } int main() { //freopen("in.txt", "r", stdin); while (cin >> n >> mod) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cin >> a[i][j], a[i][j] %= mod; } cout << det () << " "; } return 0; }