Submission #1030822

---

Source Code Expand

#include <iostream>
#include <cstdint>
#include <cassert>
#include <cstring>

uint32_t N, RK;
uint32_t C[300][300];
uint64_t pows[301];
bool zero[300];
const uint64_t MOD = 1000000007;

uint64_t memo[301][301];

uint64_t solve(int r, int rank) {
  if (memo[r][rank] != -1) {
    return memo[r][rank];
  }

  if (r == N) {
    uint64_t ans = 1;
    for (int i = rank + 1; i <= N; ++i) {
      ans = (ans * pows[N]) % MOD;
    }
    return memo[r][rank] = ans;
  } else {
    uint64_t a = (pows[N] - pows[rank] + MOD) % MOD;

    uint64_t indep = (a * solve(r + 1, rank + 1)) % MOD;
    uint64_t depen = 0;

    int nz = 0;
    if (zero[r]) {
      for (int i = 0; i < r; ++i) {
        if (zero[i]) {
          ++nz;
        }
      }
      depen = pows[nz - r + rank] * solve(r + 1, rank) % MOD;
    }

#ifdef DEBUG
    std::cout << "f(" << r << ", " << rank << ") = " << (indep + depen) << " = " << a << " * f(" << (r + 1) << ", " << (rank + 1) << ")";
    if (zero[r]) {
      std::cout << " + " << pows[nz] << " * f(" << (r + 1) << ", " << rank << ")" << std::endl;
    } else {
      std::cout << std::endl;
    }
#endif

    return memo[r][rank] = (indep + depen) % MOD;
  }
}

int main() {
  memset(memo, -1, sizeof memo);

  std::cin >> N;
  RK = N;

  pows[0] = 1;
  for (int i = 0; i <= N; ++i) {
    pows[i + 1] = (2 * pows[i]) % MOD;
  }

  for (int r = 0; r < N; ++r) {
    for (int c = 0; c < N; ++c) {
      std::cin >> C[r][c];
    }
  }

  for (int c = 0; c < N; ++c) {
    int r = 0;
    for (; r < N; ++r) {
      int t = 0;
      for (; t < c && C[r][t] == 0; ++t);
      if (t == c && C[r][t] == 1) {
        break;
      }
    }
    if (r == N) {
      zero[c] = 1;
      --RK;
    } else {
      std::swap(C[r], C[c]);
      for (int r2 = c + 1; r2 < N; ++r2) {
        if (C[r2][c] == 1) {
          for (int c2 = 0; c2 < N; ++c2) {
            if (c2 < c) {
              assert(C[r2][c2] == 0);
            } else {
              C[r2][c2] ^= C[c][c2];
            }
          }
        }
      }
    }
  }

  std::cout << solve(0, 0) << std::endl;
}

Submission Info

Judge Result