洛谷P7112 行列式求值
要是第32行的if去掉，那就喜提TLE。。。
这题限制不应该开到5秒吗，非要卡这个常数2，时间就变成两倍，直接T飞。。。害我以为做法错了，调了这么久
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 600 + 5, mod = 10000;
int a[N][N];
int p;
int f = 1;
void mygcd(int x, int y, int c, int m)
{if (a[y][c] == 0) return;int chu = a[x][c] / a[y][c];for (int j = c; j <= m; j++) a[x][j] = (a[x][j] - chu * a[y][j] % p + p) % p; swap(a[x], a[y]);f *= -1;mygcd(x, y, c, m);
}
int guess(int n, int m)
{int r = 1;for (int c = 1; c <= m; c++){int idx = r;for (int i = r + 1; i <= n; i++) {if (a[i][c]) {idx = i;f *= -1;break;}}if (a[idx][c] == 0) continue;swap(a[idx], a[r]);for (int i = r + 1; i <= n; i++) {if (a[r][c] < a[i][c]) {swap(a[r], a[i]);f *= -1;}mygcd(r, i, c, m);}r++;}return r - 1;
}
signed main()
{int n;cin >> n >> p;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {scanf("%lld", &a[i][j]);a[i][j] %= p;}}guess(n, n);int ans = 1;for (int i = 1; i <= n; i++) ans = ans * a[i][i] % p;ans = ans * f;ans = (ans % p + p) % p;cout << ans;return 0;
}
本文链接：https://my.lmcjl.com/post/7558.html
展开阅读全文
4 评论