2019 牛客暑期多校 第一场 H XOR (线性基）

题目：https://ac.nowcoder.com/acm/contest/881/H

题意：求一个集合内所有子集异或和为0的长度之和

思路：首先集合内异或和，这是线性基的一个明显标志，然后我们不管怎么样先求出一个基A,秩为r

我们枚举基外的数，每个数的贡献是  2^（n-r-1） ，为什么呢，因为其余数我都可以选择选或不选，无论什么组合，我都可以在基内表示出来，那么就肯定异或为0

我们再来枚举基A内的数，我枚举当前数的时候把其余元素再求一遍基，然后以上面相同的道理计算贡献，

#include<bits/stdc++.h>

#define maxn 100005

#define mod 1000000007

using namespace std;

typedef long long LL;

int n, r, tot;

bool vis[maxn];

vector<LL> vec;

LL a[maxn], b[], other[], tmp[];

LL qpow(LL x, int n) {

    LL res = ;

    while(n) {

        if(n & ) res = res * x % mod;

        x = x * x % mod;

        n >>= ;

    }

    return res;

}

bool ins(LL x, LL base[]) {

    for(int i = ; i >= ; --i) {

        if(x & (1LL << i)) {

            if(base[i]) x ^= base[i];

            else {

                base[i] = x;

                return true;

            }

        }

    }

    return false;

}

int main() {

    while(~scanf("%d", &n)) {

        r = tot = ;

        vec.clear();

        for(int i = ; i <= ; ++i) b[i] = other[i] = ;

        for(int i = ; i <= n; ++i) {

            scanf("%lld", &a[i]);

            vis[i] = ;

            if(ins(a[i], b)) vis[i] = , ++r, vec.emplace_back(a[i]);

        }

        if(r == n) {

            printf("0\n");

            continue;

        }

        LL ans = qpow(, n - r - ) * (n - r) % mod;;

        for(int i = ; i <= n; ++i) {

            if(vis[i]) continue;

            ins(a[i], other);

        }

        for(int i = ; i < vec.size(); ++i) {

            tot = ;

            for(int j = ; j <= ; ++j) tmp[j] = ;

            for(int j = ; j < vec.size(); ++j) {

                if(i == j) continue;

                if(ins(vec[j], tmp)) ++tot;

            }

            for(int j = ; j <= ; ++j) {

                if(other[j] && ins(other[j], tmp)) ++tot;

            }

            if(!ins(vec[i], tmp)) {

                ans = (ans + qpow(, n - tot - )) % mod;

            }

        }

        printf("%lld\n", ans);

    }

    return ;

}