Submission #3671099

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=3000+10,mod=1e9+7;
bitset<maxn> C,Bas[maxn];
bool vis[maxn];
int Pw[maxn],dp[maxn][maxn];
int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=(ll)res*x%mod;
		x=(ll)x*x%mod;
		y>>=1;
	}
	return res;
}
int main(){
	int n=read(),R=0;
	REP(i,1,n){
		REP(j,1,n) C[j]=read();
		REP(j,1,n) if(C[j]){
			if(vis[j]) C^=Bas[j];
			else{
				vis[j]=1,Bas[j]=C;
				++R;
				break;
			}
		}
	}
	Pw[0]=1;
	REP(i,1,n) Pw[i]=(Pw[i-1]<<1)%mod;
	dp[0][0]=1;
	REP(i,1,n) REP(j,0,i){
		dp[i][j]=(ll)dp[i-1][j]*Pw[j]%mod;
		if(j) dp[i][j]=(dp[i][j]+(ll)dp[i-1][j-1]*(Pw[n]-Pw[j-1]+mod))%mod;
	}
	int ans=0;
	REP(i,R,n) ans=(ans+(ll)dp[n][i]*ksm(2,n*(n-i))%mod*dp[i][R])%mod;
	ans=(ll)ans*ksm(dp[n][R],mod-2)%mod;
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result