Submission #1001076

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define P 1000000007
#define N 310
int n;
int C[N][N];
int P2[N];

void gcd(int a,int b,int &x,int &y) {
  if(b==0){x=1,y=0;return;}
  gcd(b,a%b,y,x),y-=a/b*x;
}
int inv(int n) {
  int x,y;gcd(n,P,x,y);
  if(x<0)x+=P;return x;
}

ll f[N][N];

ll ff(int m, int r) {
	if (r < 0) return 0;
	if (r > m) return 0;
	if (m == 0) return 1;
	if (f[m][r] != -1) return f[m][r];
	ll S = 0;
	// Case 1: last is in
	
	ll T1 = 0;
	T1 = ff(m-1, r);
	T1 = (ll)T1 * P2[r]%P;
	
	// Case 2: last is not in
	ll T2 = 0;
	T2 = ff(m-1,r-1);
	ll C = P2[n] - P2[r-1];
	if (C < 0) C += P;
	T2 = (ll)T2 * C %P;
	//cout << m << " " << r << " " << T1 << " " << T2 << endl;
	
	S = (T1 + T2)%P;
	
	f[m][r] = S;
	return S;
}

ll gg(int n, int m) {
	if (m > n) return 0;
	ll S = 1;
	for (int i = 0; i < m; i ++) {
		ll T = P2[n] - P2[i];
		if (T < 0) T += P;
		S = (ll)S*T%P;
	}
	for (int i = 0; i < m; i ++) {
		ll T = P2[m] - P2[i];
		if (T < 0) T += P;
		S = (ll)S*inv(T)%P;
	}
	return S;
}

int main () {
	P2[0] = 1;
	for (int i = 1; i < N; i ++) P2[i] = P2[i-1]*2%P;
	cin >> n;
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < n; j ++)
			cin >> C[i][j];
	int nw = 0;
	for (int i = 0; i < n; i ++) {
		for (int j = i; j < n; j ++) {
			if (C[j][i]) {
				for (int k = 0; k < n; k ++)
					swap(C[nw][k], C[j][k]);
				break;
			}
		}
		if (!C[nw][i]) continue;
		for (int j = nw+1; j < n; j ++)
			if (C[j][i]) {
				for (int k = 0; k < n; k ++)
					C[j][k] ^= C[nw][k];
			}
		nw++;
	}
	//cout << nw << endl;
	for (int i = 0; i <= n; i ++)
		for (int j = 0; j <= n; j ++) f[i][j] = -1;
	ll S = 0;
	for (int rk = 0; rk <= n; rk ++) {
		ll T = ff(n, rk); // #mat with rk r
		ll T1 = gg(n, nw); // #nw subsp in n
		ll T2 = gg(rk, nw); // #nw subsp in rk
		ll TP = (ll) T2 * inv(T1)%P; // prob contain subsp
		T = (ll)T*TP%P;
		for (int i = 0; i < n; i ++) { // fixed
			T = (ll)T*P2[n-rk]%P;
		}
		/*
		for (int i = nw; i < n; i ++) { // any
			T = (ll)T*P2[n]%P;
		}
		*/
		(S += T) %= P;
	}
	cout << S << endl;
	return 0;
}

Submission Info

Judge Result