Untitled
CPP
views 17
,
size 2120 b
``````#include <bits/stdc++.h>
//#define IOFILE
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define ALL(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
constexpr ll MOD = 100000007;

ll power(ll a, ll b) {
ll ret = 1;
for(; b; a = a * a % MOD, b >>= 1)
if(b & 1)
ret = ret * a % MOD;
return ret;
}

const int maxn = 12;
int n;
vector<vector<ll>> matrix;

ll calc() {
ll ret = 1;
for(int i = 0; i < n; ++i) {
int idx = i;
while(idx < n && matrix[idx][i] == 0)
idx++;
if(idx == n) return 0;
if(idx != i)
ret = -ret;
if(ret < 0)
ret += (abs(ret) / MOD + 1) * MOD;
swap(matrix[idx], matrix[i]);
ret = ret * matrix[i][i] % MOD;
ll tmp = matrix[i][i];
for(int j = i; j < n; ++j)
matrix[i][j] = matrix[i][j] * power(tmp, MOD - 2) % MOD;
for(int j = i + 1; j < n; ++j) if(matrix[j][i] != 0) {
tmp = matrix[j][i];
for(int k = i; k < n; ++k) {
matrix[j][k] = (matrix[j][k] - tmp * matrix[i][k] + MOD) % MOD;
if(matrix[j][k] < 0)
matrix[j][k] += (abs(matrix[j][k]) / MOD + 1) * MOD;
}
}
}
return (ret + MOD) % MOD;
}

inline void solve() {
while(cin >> n) {
matrix = vector<vector<ll>>(n, vector<ll>(n));
for(auto& x : matrix) for(auto& y : x)
cin >> y;
cout << calc() << '\n';
}
}

int main() {
#ifndef IOFILE
cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);
#endif
#ifdef IOFILE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("err.txt", "w", stderr);
clock_t time = clock();
#endif
int t = 1;
// cin >> t;
while(t--) {
solve();
}

#ifdef IOFILE
cout << "\nUse " << static_cast<double>(clock() - time) / CLOCKS_PER_SEC << " seconds";
#endif
}``````