线性基算贡献——19牛客多校第一场H

/*
给定数组a[],求有多少集合的异或值为0，将这些集合的大小之和求出来
对于每个数来说，如果除去这个数后数组里做出的线性基和这个数线性相关，那么这个数贡献就是2^(n-1-线性基的大小)
反之这个数和线性基线性无关，即数组里凑不出这个数来和其异或等于0，所以贡献就是0 由于做n次线性基很麻烦，所以简化问题，只需要先做出一个基，将数分成在基内和基外即可
首先做出一个线性基base，设其大小为r
然后分情况来讨论：
1.对于线性基外的每个数，其贡献是2^(n-r-1)
2.对于每个线性基内的数字ai，做一个除去ai的线性基base'
如果base'和ai线性相关，那么ai的贡献就是2^(n-r-1),
反之ai和base'线性无关，贡献是0
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define mod 1000000007
struct LB{
ll b[],r;
void clear(){for(int i=;i>=;i--)b[i]=;r=;}
void insert(ll x){
for(int i=;i>=;i--)if(x>>i & ){
if(!b[i]){
b[i]=x;r++;break;
}
x^=b[i];
}
}
int check(ll x){
for(int i=;i>=;i--)if(x>>i & ){
if(!b[i])return ;
x^=b[i];
}
return ;
}
}base,tmp,tmp2;
ll n,a[maxn],flag[maxn],flag2[maxn];ll Pow(ll a,ll b){
ll res=;
while(b){
if(b%)res=res*a%mod;
b>>=;a=a*a%mod;
}
return res;
}int main(){
while(scanf("%lld",&n)!=EOF){
ll ans=;
memset(flag,,sizeof flag);
base.clear();tmp.clear();
for(int i=;i<=n;i++)scanf("%lld",&a[i]);
for(int i=;i<=n;i++)
if(base.check(a[i])){
base.insert(a[i]);
flag[i]=;
}
//在base之外再做一个线性基
for(int i=;i<=n;i++)
if(!flag[i])tmp.insert(a[i]); ll P=Pow(,n-base.r-); for(int i=;i<=n;i++)
if(!flag[i])//在线性基base外
ans=(ans+P)%mod;
else {//在线性基内
tmp2=tmp;
for(int j=;j<=n;j++)
if(flag[j]&&j!=i)tmp2.insert(a[j]);
if(tmp2.check(a[i])==)
ans=(ans+P)%mod;
}
cout<<ans<<endl;
}
}