-
Notifications
You must be signed in to change notification settings - Fork 0
/
线性基求交.cpp
65 lines (57 loc) · 1.17 KB
/
线性基求交.cpp
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
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
void Insert(ll *base,ll x)
{
for(int i=32;i >= 0;--i)
if(x>>i&1)
{
if(!base[i])
{
base[i]=x;
return ;
}
x ^= base[i];
}
}
void Merge(ll *a,ll *b,ll *c)///c = a ∩ b
{
ll all[40];
ll B[40];
for(int i=0;i <= 32;++i)
all[i]=a[i];
mem(B,0);
mem(c,0);
for(int i=32;i >= 0;--i)
{
ll x=b[i];
ll y=b[i];
for(int j=32;j >= 0;--j)
if(x>>j&1)
{
if(!all[j])
{
all[j]=x;
B[j]=y;
break;
}
x ^= all[j];
y ^= B[j];///消除B的影响,使得y仅由基A表示
}
if(!x)///如果x未插入到all中,那么 y ∈ c
Insert(c,y);
}
}
ll a[40],b[40],c[40];
int main()
{
Insert(a,5);
Insert(b,1);
Insert(b,4);
Merge(a,b,c);
///输出 5
for(int i=0;i <= 32;++i)
if(c[i])
printf("%lld ",c[i]);
}