H - AB=C Problem
Time limit : 3sec / Memory limit : 256MB

Score : 1500 points

Problem Statement
Snuke received two matrices A and B as birthday presents. Each of the matrices is an N by N matrix that consists of only 0 and 1.

Then he computed the product of the two matrices, C=AB. Since he performed all computations in modulo two, C was also an N by N matrix that consists of only 0 and 1. For each 1≤i,j≤N, you are given ci,j, the (i,j)-element of the matrix C.

However, Snuke accidentally ate the two matrices A and B, and now he only knows C. Compute the number of possible (ordered) pairs of the two matrices A and B, modulo 109+7.

Constraints
1≤N≤300
ci,j is either 0 or 1.

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

const int M = 305;
const ll p = 1e9+7;

int c[M][M], n, r;
ll p2[M*M], dp[M][M];

ll ans = 0;

int compr() {
    for (int i = 0; i < n; ++i) {
        int ind = -1, m = n;
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < n; ++k)
                if (c[j][k] == 1) {
                    if (k < m)
                        m = k, ind = j;
                    break;
                }
        }
        if (ind == -1)
            return i;
        for (int j = 0; j < n; ++j)
            swap(c[i][j], c[ind][j]);
        for (int j = i+1; j < n; ++j)
            if (c[j][m] == 1)
                for (int k = 0; k < n; ++k)
                    c[j][k] ^= c[i][k];
    }

    return n;
}

int main() {
    p2[0] = 1;
    for (int i = 1; i < M*M; ++i)
        p2[i] = 2*p2[i-1]%p;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> c[i][j];

    r = compr(); // cout << r << endl;
    dp[r][r] = 1;

    for (int i = 1; i <= r; ++i)
        dp[r][r] = dp[r][r]*(p+p2[n]-p2[i-1])%p;

    for (int i = r; i <= n-1; ++i)
        for (int j = r; j <= n-1; ++j) {
            dp[i+1][j] += dp[i][j]*p2[j-r];
            dp[i+1][j] %= p;
            dp[i+1][j+1] += dp[i][j]*(p+p2[n]-p2[j]);
            dp[i+1][j+1] %= p;
        }

    for (int i = 0; i <= n; ++i) {
        ans += dp[n][i]*p2[n*(n-i)];
        ans %= p;
    }

    cout << ans << endl;
}