Submission #20009616

---

Source Code Expand

#include<bits/stdc++.h>
#define PB emplace_back
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 300, mod = 1e9 + 7;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0; bool f = false;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
	if(f) x = -x;
}
template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
template<typename T>
bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
void qmo(int &x){x += x >> 31 & mod;}
int ksm(int a, int b){
	int res = 1;
	for(;b;b >>= 1, a = (LL)a * a % mod)
		if(b & 1) res = (LL)res * a % mod;
	return res;
}
int n, r, pw2[N], dp[N][N], ans; bool vis[N];
bitset<N> bas[N], tmp;
int main(){
	read(n);
	for(int i = 0;i < n;++ i){
		for(int j = 0, ch;j < n;++ j){
			do ch = getchar(); while(ch != '0' && ch != '1');
			tmp[j] = ch - '0';
		}
		for(int j = 0;j < n;++ j) if(tmp[j]){
			if(vis[j]) tmp ^= bas[j];
			else {vis[j] = true; bas[j] = tmp; ++ r; break;}
		}
	} pw2[0] = 1;
	for(int i = 1;i <= n;++ i) qmo(pw2[i] = pw2[i-1] * 2 - mod);
	dp[0][0] = 1;
	for(int i = 0;i < n;++ i)
		for(int j = 0;j <= i;++ j){
			dp[i+1][j] = (dp[i+1][j] + (LL)dp[i][j] * pw2[j]) % mod;
			dp[i+1][j+1] = (dp[i+1][j+1] + (LL)dp[i][j] * (pw2[n] - pw2[j] + mod)) % mod;
		}
	for(int i = r;i <= n;++ i) ans = (ans + (LL)dp[n][i] * dp[i][r] % mod * ksm(2, n*(n-i))) % mod;
	printf("%lld\n", (LL)ans * ksm(dp[n][r], mod-2) % mod);
}

Submission Info

Judge Result