线性基模板
Apale 7/28/2019
存个板子
typedef long long ll;
struct base
{
ll a[63];
vector<ll> p;
bool flag;//标记答案集合中是否有0
base()
{
fill(a, a + 63, 0ll);
flag = false;
}
void init()
{
fill(a, a + 63, 0ll);
p.clear();
flag = false;
}
bool insert(ll val)
{
ll t = 1ll << 62;
for (int i = 62; ~i; --i)
{
if (val & t)
{
if (!a[i])
{
a[i] = val;
return true;
}
val ^= a[i];
}
t >>= 1;
}
flag = true;//能到这里说明能异或出0
return false;
}
ll query_max()
{
ll ans = 0;
for (int i = 62; ~i; --i)
if ((ans ^ a[i]) > ans)
ans ^= a[i];
return ans;
}
ll query_min()
{
for (int i = 0; i <= 62; ++i)
{
if (a[i])
return a[i];
}
return 0;
}
void rebuild()
{
ll t;
for (int i = 62; ~i; --i)
{
if (!a[i]) continue;
t = 1ll << i - 1;
for (int j = i - 1; ~j; --j, t >>= 1)
if (a[i] & t)
a[i] ^= a[j];
}
for (int i = 0; i <= 62; ++i)
if (a[i])
p.push_back(a[i]);
}
ll kth(ll k)
{
if (flag) --k;//答案集合中有0
ll ans = 0;
if (k >= (1ll << p.size()))
return -1;
ll t = 1ll << 62;
for (int i = 62; ~i; --i, t >>= 1)
if (k & t)
ans ^= p[i];
return ans;
}
inline ll &operator[](int i)
{
return a[i];
}
base operator+(base &b) const
{
base ans = *this;
for (int i = 0; i <= 62; ++i)
if (b[i])
ans.insert(b[i]);
return ans;
}
};
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
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