Untitled
raw download clone
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
}
close fullscreen
Login or Register to edit or fork this paste. It's free.