前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2019 牛客多校 第一场 H、XOR

2019 牛客多校 第一场 H、XOR

作者头像
用户2965768
发布2019-08-01 10:47:23
3900
发布2019-08-01 10:47:23
举报
文章被收录于专栏:wym

题解

代码语言:javascript
复制
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9+7;
ll c[100],c2[100],temp[100];
ll a[100005];
bool vis[100005];
int cnt,cnt2;
int n;
ll quick(ll x,ll y){
	ll res = 1;
	while(y){
		if(y&1){
			res=res*x%mod;
		}
		y>>=1;
		x=x*x%mod;
	}
	return res;
}
bool add(ll bs[],ll x){
	for(int i=63;i>=0;i--){
		if(x&(1ll<<i)){
			if(!bs[i]){
				bs[i] =  x;
				return true;
			}
			x^=bs[i];
		}
	}
	return false;
} 
int main()
{
	
	while(scanf("%lld",&n)>0){
		vector<ll> v;
		v.clear();
		for(int i=100;i>=0;i--)c[i]=0,c2[i]=0,temp[i] = 0;
		cnt=0;	cnt2 = 0;
		memset(vis,false,sizeof(vis));
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			if(add(c,a[i])){
				cnt++;
				v.push_back(a[i]);
				vis[i] = 1;
			}		
		}	
		if(v.size()==n){
			printf("0\n");
			continue;
		} 
		ll ans=(n-cnt)*quick(2,n-cnt-1)%mod;
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				if(add(c2,a[i]))
				cnt2++;
			}
		}
		int len = v.size();
		for(int i=0;i<len;i++){
			cnt = cnt2;
			for(int j=0;j<64;j++){
				temp[j] = c2[j];	
			}
			for(int j=0;j<len;j++){
				if(i!=j){
					if(add(temp,v[j])){
						cnt++;
					}
				}	
			}
			if(!add(temp,v[i])){
				ans+=quick(2,n-cnt-1);
				if(ans>=mod)ans-=mod;
			}
		}
		printf("%lld\n",ans%mod);
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月24日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档