Submission #1001066

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod=1000000007;
typedef vector<vector<int> >mat;
int getrank(mat m)
{
	int r=0;
	for(int i=0;i<m.size();i++)
	{
		for(int j=r;j<m.size();j++)
		{
			if(m[j][i]==1)
			{
				swap(m[r],m[j]);
				for(int k=r+1;k<m.size();k++)
				{
					if(m[k][i]==1)
					{
						for(int l=0;l<m.size();l++)m[k][l]^=m[r][l];
					}
				}
				r++;
				break;
			}
		}
	}
	return r;
}
ll po(ll a,ll b)
{
	if(b==0)return 1;
	ll z=po(a,b/2);
	z=z*z%mod;
	if(b%2==1)z=z*a%mod;
	return z;
}
ll inv(ll a)
{
	return po(a,mod-2);
}
ll dp[500][500];//rank rの行列の数
ll db[500];//d次元subvectorspaceの数
ll p2[500];
ll inv2[500][500];
int main()
{
	int num;
	scanf("%d",&num);
	mat m;
	m.resize(num);
	for(int i=0;i<num;i++)
	{
		for(int j=0;j<num;j++)
		{
			int z;
			scanf("%d",&z);
			m[i].push_back(z);
		}
	}
	int r=getrank(m);
	p2[0]=1;
	for(int i=1;i<500;i++)p2[i]=p2[i-1]*2%mod;
	dp[0][0]=1;
	for(int i=0;i<num;i++)
	{
		for(int j=0;j<num;j++)
		{
			dp[i+1][j]+=dp[i][j]*p2[j];
			dp[i+1][j+1]+=dp[i][j]*(p2[num]+mod-p2[j]);
			dp[i+1][j]%=mod;
			dp[i+1][j+1]%=mod;
		}
	}
	for(int i=0;i<500;i++)for(int j=0;j<500;j++)inv2[i][j]=inv((p2[i]+mod-p2[j])%mod);
	for(int i=0;i<=num;i++)
	{
		ll x=1;
		for(int j=0;j<i;j++)
		{
			x*=(p2[num]+mod-p2[j]);
			x%=mod;
		}
		for(int j=0;j<i;j++)
		{
			x*=inv2[i][j];
			x%=mod;
		}
		db[i]=x;
	}
	ll ans=0;
	for(int a=r;a<=num;a++)
	{
		for(int b=r;b<=num&&a+b-num<=r;b++)
		{
			int s=r,t=b-r,u=(num-a)-(b-r);
			//printf("%d %d %d\n",s,t,u);
			ll x=1;
			for(int i=0;i<s+t+u;i++)
			{
				x*=(p2[num]+mod-p2[i]);
				x%=mod;
			}
			for(int i=0;i<t;i++)
			{
				x*=inv2[t][i];
				x%=mod;
			}
			for(int i=0;i<s;i++)
			{
				x*=inv2[s+t][i+t];
				x%=mod;
			}
			for(int i=0;i<u;i++)
			{
				x*=inv2[u+t][i+t];
				x%=mod;
			}
			ll kak=x*inv(db[a])%mod*inv(db[b])%mod;
			//printf("%d %d %lld %lld %lld\n",a,b,x,kak,dp[num][a]*dp[num][b]%mod*kak%mod);
			ans+=dp[num][a]*dp[num][b]%mod*kak;
			ans%=mod;
		}
	}
	printf("%lld\n",ans*inv(dp[num][r])%mod);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&num);
                  ^
./Main.cpp:59:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&z);
                  ^

Judge Result