Submission #1024078

---

Source Code Expand

#include <algorithm>

#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>

#include <vector>
#include <iostream>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const llint mod = 1e9 + 7;
const int MAXN = 321;

llint pot2[MAXN];
int dp[MAXN][MAXN][MAXN]; // rows, columns, rank

llint indep_vects(int dim, int k) {
  llint ans = 1;
  REP(i, k) {
    ans *= (pot2[dim] - pot2[i] + mod) % mod;
    ans %= mod;
  }
  return ans;
}

llint power_mod(llint b, llint e) {
  llint ans = 1;
  llint p2 = b;
  for (; e; e >>= 1) {
    if (e&1) ans = ans*p2 % mod;
    p2 = p2*p2 % mod;
  }
  return ans;
}

llint mod_inv(llint x) {
  return power_mod(x, mod-2);
}

llint k_subspaces(int dim, int k) {
  return (llint)dp[dim][dim][dim-k] * mod_inv( indep_vects(dim, dim-k) ) % mod;
}

int get_matrix_rank(int C[][MAXN], int n) {
  int rank = 0;

  REP(j, n) {
    int tmp_row = -1;
    FOR(i, rank, n) if (C[i][j] != 0) { tmp_row = i; break; }
    if (tmp_row == -1) {
      
    } else {
      REP(k, n) swap(C[rank][k], C[tmp_row][k]);
      assert(C[rank][j] == 1);

      REP(r2, n) if (r2 != rank)
        if (C[r2][j])
          REP(k, n)
            C[r2][k] ^= C[rank][k];
            
      ++rank;
    }
  }

  return rank;
}

int main(void) {
  pot2[0] = 1;
  for (int i = 1; i < MAXN; ++i) pot2[i] = (pot2[i-1] * 2) % mod;

  int n;
  static int C[MAXN][MAXN];
  scanf("%d", &n);
  REP(i, n) REP(j, n) scanf("%d", C[i]+j);

  //  TRACE(n);
  //  TRACE(pot2[0] _ pot2[10]);
  
  //  TRACE(power_mod(2, 0));
  //  TRACE(power_mod(2, 1));
  //  TRACE(power_mod(2, 2));
  //  TRACE(power_mod(2, 3));

  //  TRACE(indep_vects(n, 0));
  //  TRACE(indep_vects(n, 1));
  //  TRACE(indep_vects(n, 2));
  //  TRACE(indep_vects(n, 3));

  //  TRACE(mod_inv(5) _ 5 * mod_inv(5) % mod);

  memset(dp, 0, sizeof dp);
  REP(rows, MAXN-1) {
    dp[rows][0][0] = 1;

    REP(c, MAXN-1) REP(r, MAXN-1) {
      if (dp[rows][c][r] == 0) continue;

      dp[rows][c+1][r+1] += (pot2[rows] - pot2[r] + mod) % mod * (llint)dp[rows][c][r] % mod;
      dp[rows][c+1][r+1] %= mod;

      dp[rows][c+1][r] += pot2[r] * (llint)dp[rows][c][r] % mod;
      dp[rows][c+1][r] %= mod;
    }
  }

  int rankC = get_matrix_rank(C, n);
  //  TRACE(rankC);
  //  TRACE(dp[n][n][n]);

  //  TRACE(k_subspaces(n, 0));
  //  TRACE(k_subspaces(n, 1));
  //  TRACE(k_subspaces(n, 2));
  //  TRACE(k_subspaces(n, 3));

  int kerC = n - rankC;
  llint ans = 0;
  FOR(kerB, 0, kerC+1) {
    llint val = k_subspaces(kerC, kerB);
    val = val*indep_vects(n, n-kerB) % mod;
    val = val*power_mod(pot2[n], kerB) % mod;
    ans = (ans + val) % mod;

    //    TRACE(kerB _ val);
  }

  printf("%lld\n", ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:84:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i, n) REP(j, n) scanf("%d", C[i]+j);
                                          ^

Judge Result