传送门

题意

给\(n\)个数，计算所有异或和为\(0\)的子集大小之和。

思路

首先要把计算所有子集的大小之和这个问题转变一下，求每个数处在的异或和为\(0\)的子集的个数的和。
然后求这\(n\)个数的线性基\(B_1\)，设\(B_1\)的秩为\(R\)，这里对于线性基熟悉的老哥能发现：对于原\(n\)个数的任意子集，\(B_1\)中的\(R\)个数有且仅有\(1\)个子集与之异或和相等。
所以对于每个不在\(B_1\)里的数\(x\)，可以从除\(x\)和\(B_1\)的\(n-R-1\)个数中任意选一个子集\(S\)，对应\(B_1\)中有且仅有\(1\)个子集\(s\)与\(\{x\}\cup S\)异或和相等，所以\(s\cup \{x\}\cup S\)是对于\(x\)的一个子集，而\(x\)对应\(2^{n-R-1}\)个\(S\)，每个\(S\)只对应\(1\)个\(s\)。所以对于除\(B_1\)外的\(n-R\)个数，累计有\((n-R)*2^{n-R-1}\)。
然后考虑\(B_1\)中的每个数\(x\)，对除它以外的\(n-1\)个数求出线性基\(B_3\)，如果\(x\)不能被\(B_3\)表示的话，显然它不会参与任何子集。否则同样也会对答案产生\(2^{n-R-1}\)的贡献。
关于如何快速求出\(B_3\)：先对除\(B_1\)的\(n-R\)个数求除线性基\(B_2\)，然后枚举\(B_1\)中的数\(x\)，每次\(B_3=B_2\)，然后将除\(x\)的\(R-1\)个数加入\(B_3\)就可以了。

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
const int N=3e5+10;
const int mod=1e9+7;
inline LL qpow(LL x,LL k=mod-2,LL m=mod){LL res=1;while(k){if(k&1) res=res*x%m;x=x*x%m;k>>=1;}return res;}
int n,ins[N];LL a[N];
vector<LL> bs;

struct LB{
    LL b[70];bool zero;int R;
    void init(){memset(b,0,sizeof(b));zero=R=0;}
    bool insert(LL x){
        if(x==0) zero=1;
        for(int i=63;i>=0;i--){
            if(!(x>>i&1)) continue;
            if(!b[i]){b[i]=x;R++;return 1;}
            x^=b[i];
        }
        return 0;
    }
}B1,B2,B3;

void solve(){
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    B1.init();B2.init();B3.init();bs.clear();
    for(int i=1;i<=n+5;i++) ins[i]=0;
    for(int i=1;i<=n;i++) {
        ins[i]=B1.insert(a[i]);
        if(ins[i]) bs.pb(a[i]);
    }
    LL ans=1ll*(n-B1.R)*qpow(2,n-B1.R-1)%mod;
    for(int i=1;i<=n;i++) if(!ins[i]) B2.insert(a[i]);
    for(int i=0;i<bs.size();i++){
        B3=B2;
        for(int j=0;j<bs.size();j++){
            if(i==j) continue;
            B3.insert(bs[j]);
        }
        int res=B3.insert(bs[i]);
        if(res) continue;
        ans=(ans+qpow(2,n-B3.R-1))%mod;
    }
    printf("%lld\n",ans); 
}

int main(){
    while(~scanf("%d",&n)) solve();
    return 0;
}