题目：2019牛客多校第一场 H.XOR

题目大意：

给你一个序列，问所有它的异或和为 0 的子集大小之和。

\left(\sum_{S \subseteq A, \oplus_{x \in S} x = 0} |S|\right) \bmod (10^9+7)

解题思路：

先对 n 个元素构造线性基 LB1，设其大小为 r 。考虑不在线性基中每一个元素的贡献，其与任意不在线性基中的 n-r-1 个元素组合，均可以在线性基中唯一找到与它异或和为 0 的方案。因此它们的贡献都是 2^{n-r-1}
考虑线性基中元素的贡献。如果某个元素在另一组线性基中不存在，那么它的贡献就等同于不在线性基中的元素；如果它一定在线性基中，则如果选它，一定不可能异或和为 0 ，所以贡献为 0 。
那如何判断呢？我们可以对 n-r-1 个元素构造一个线性基 LB2，每次将 LB2 赋值给另一个线性基 LB3。判断 LB1 中元素 i 是否不可替代，我们可以将 LB1中除了 i 以外的元素先插入 LB3 中，再尝试插入 i ：如果插入成功，说明 i 不可替代，贡献为 0；否则可替代。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
const int N = 1e5 + 50;
const int M = 62;
int n;
long long a[N], ans;
long long pow2[N];

struct Linear_Base {
    long long d[100]; int tot;
    void init() {
        tot = 0;
        memset(d, 0, sizeof(d));
    }
    bool insert(long long x) {
        for (int i = M; i >= 0; i--) {
            if (!(x >> i)) continue;
            if(!d[i]) {
                d[i] = x; tot++; break;
            }
            x ^= d[i];
        }
        return x > 0;
    }
}LB1, LB2, LB3;

vector<long long> LB;
int vis[N];

void init() {
    pow2[0] = 1;
    for (int i = 1; i < N; i++) pow2[i] = pow2[i-1] * 2 % P;
}

void clear() {
    ans = 0; LB.resize(0);
    LB1.init(); LB2.init(); LB3.init();
    memset(vis, 0, sizeof(vis));
}

int main() {
    init();
    while (~scanf("%d", &n)) {
        clear();
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            if (LB1.insert(a[i])) {
                LB.push_back(a[i]); vis[i] = 1;
            }
        }
        ans = pow2[n - LB1.tot - 1] * (n - LB1.tot) % P;
        for (int i = 1; i <= n; i++) {
            if(!vis[i]) LB2.insert(a[i]);
        }
        for (int i = 0; i < LB1.tot; i++) {
            LB3 = LB2;
            for (int j = 0; j < LB1.tot; j++) {
                if (i != j) LB3.insert(LB[j]);
            }
            if (!LB3.insert(LB[i])) {
                (ans += pow2[n - LB1.tot - 1]) %= P;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}