Top

线性基模板


博主CSDN

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn=1e5+7;
const int mod=1e9+7;
struct Linear_Basis{
ll b[63],nb[63],tot; //b为线性基 nb用来求第K小异或值 tot为nb元素个数
bool flag=false;
void Init(){ //初始化
tot=0;
flag=false;
memset(b,0,sizeof(b));
memset(nb,0,sizeof(nb));
}
void Ins(ll x){ //插入
for(int i=62;i>=0;i--){
if(x&(1ll<<i)){
if(!b[i]){
b[i]=x;
return;
}
x^=b[i];
}
}
flag=true;
return;
}
bool Fin(ll x){ //验证存在性
if(x==0&&b[0])return 1;
for(int i=62;i>=1;i--){
int j=i-1;
if(x&(1<<j)){
x^=b[i];
if(!x)return 1;
}
}
return 0;
}
ll Max(ll x){ //求最大值
ll res=x;
for(int i=62;i>=0;i--){
res=max(res,res^b[i]);
}
return res;
}
ll Min(ll x){ //求最小值
ll res=x;
for(int i=0;i<=62;i++){
if(b[i])res^=b[i];
}
return res;
}
ll Rebuild(){ //第K大
for(int i=62;i>=0;i--){
if(b[i]==0)continue;
for(int j=i-1;j>=0;j--){
if(b[j]==0)continue;
if(b[i]&(1ll<<j))b[i]^=b[j];
}
}
for(int i=0;i<=62;i++){
if(b[i])nb[tot++]=b[i];
}
}
ll Kth_Max(ll k){
if(flag)k--; //???
ll res=0;
if(k==0)return 0;
if(k>=(1ll<<tot))return -1;
for(int i=62;i>=0;i--){
if(k&(1ll<<i))res^=nb[i];
}
return res;
}
}LB;
void merge(Linear_Basis &a,Linear_Basis &b){//a和b都变成a+b
for(int i=31;i>=1;i--){
if(b.b[i]==0)continue;
a.Ins(b.b[i]);
}
b=a;
}
int main(){
int n;
scanf("%d",&n);
return 0;
}