AtCoder Regular Contest 054 C: 鯛焼き

問題

C: 鯛焼き - AtCoder Regular Contest 054 | AtCoder

解法

http://arc054.contest.atcoder.jp/data/arc/054/editorial.pdf

コード

#include <bits/stdc++.h>
using namespace std;

int64_t extgcd(int64_t a, int64_t b, int64_t &x, int64_t &y) {
  int64_t d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

int64_t mod_inverse(int64_t a, int64_t m) {
  int64_t x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}

int64_t det(vector<vector<int>> A, const int64_t MOD) {
  int n = A.size();
  assert(n == A[0].size());
  int64_t ans = 1;
  for (int i = 0; i < n; i++) {
    int pivot = i;
    while (pivot < n && !A[pivot][i]) pivot++;
    if (pivot == n) return 0;
    if (i != pivot) {
      swap(A[i], A[pivot]);
      ans *= -1;
    }

    int64_t inv = mod_inverse(A[i][i], MOD);
    for (int j = i + 1; j < n; j++) {
      int64_t c = A[j][i] * inv % MOD;
      for (int k = i; k < n; k++) {
        A[j][k] = (A[j][k] - c * A[i][k]) % MOD;
      }
    }
  }

  for (int i = 0; i < n; ++i) ans = (ans * A[i][i]) % MOD;
  if (ans < 0) ans += MOD;
  return ans;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<vector<int>> M(N, vector<int>(N, 0));
  for (int i = 0; i < N; ++i) {
    string S;
    cin >> S;
    for (int j = 0; j < N; ++j) {
      if (S[j] == '1') M[i][j] = 1;
    }
  }

  cout << (det(M, 2) ? "Odd" : "Even") << endl;
}