XOR

Posted on | In , , ,

题目链接

题意

计算所有异或起来为0的集合的集合大小之和。即

思路

考虑计算每个数字的贡献。
即数字能参与多少个集合使集合异或和为0。
我们先建出整个序列的线性基，那么那些不在线性基里的元素都能被表示，假设我对任何不在线性基里的元素取或不取，整个集合我都可以使异或和为0.
为什么呢？因为这是线性基能唯一表示一个数字的特点。那么如果线性基里的元素我都取，其他任取，元素$i$的贡献为。
对于那些在线性基中的元素，我去检查一下除他以外的数字构成的线性基，用同样的方法去搞一遍。

主要要理解线性基这个工具他可以确定哪些元素是我可以任选，哪些元素是要看其他数字是否都还有的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
 
const int N = 1e5 + 5;
ll a[N];
ll base[65];
const ll mod = 1e9 + 7;
vector<ll> v;
bool vis[N];
ll bsc[N];
ll tmp[N];
ll Pow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        int tot = 0;
        v.clear();
        for (int i = 1; i <= n; i++)
            vis[i] = 0;
        for (int i = 0; i < 64; i++)
            base[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            ll x = a[i];
            for (int j = 63; j >= 0; j--)
            {
                if ((x >> j) & 1)
                {
                    if (!base[j])
                    {
                        base[j] = x;
                        tot++;
                        vis[i] = true;
                        v.push_back(a[i]);
                        break;
                    }
                    else
                    {
                        x ^= base[j];
                    }
                }
            }
        }
        ll ans = Pow(2ll, n - tot - 1) * (n * 1ll - tot) % mod;
        dbg(ans);
        for (int j = 0; j < 64; j++)
            bsc[j] = 0;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (vis[i])
                continue;
            ll x = a[i];
            for (int j = 63; j >= 0; j--)
                if ((x >> j) & 1)
                {
                    if (!bsc[j])
                    {
                        bsc[j] = x;
                        cnt++;
                        break;
                    }
                    else
                    {
                        x ^= bsc[j];
                    }
                }
        }
        for (auto &val : v)
        {
            for (int j = 0; j < 64; j++)
                tmp[j] = bsc[j];
            int tcnt = cnt;
            for (auto & vv : v)
                if (vv != val)
                {
                    ll x = vv;
                    for (int j = 63; j >= 0; j--)
                        if ((x >> j) & 1)
                        {
                            if (!tmp[j])
                            {
                                tmp[j] = x;
                                tcnt++;
                                break;
                            }
                            else
                            {
                                x ^= tmp[j];
                            }
                        }
                }
            ll x = val;
            for (int j = 63; j >= 0; j--)
                if ((x >> j) & 1)
                {
                    if (!tmp[j])
                    {
                        tmp[j] = x;
                        break;
                    }
                    else
                    {
                        x ^= tmp[j];
                    }
                }
            dbg(val, x);
            if (x == 0)
                ans = (ans + Pow(2, n - tcnt - 1)) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
0%