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
| struct Bitset
{
unsigned a[1600];
void reset()
{
memset(a,0,sizeof(a));
}
Bitset()
{
reset();
}
void flip(int x)
{
a[x>>5]^=1<<(x&31);
}
void set(int x)
{
a[x>>5]|=1<<(x&31);
}
void reset(int x)
{
a[x>>5]&=~(1<<(x&31));
}
int test(int x)
{
return (a[x>>5]>>(x&31))&1;
}
Bitset operator ~()const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=~a[i];
return ret;
}
Bitset operator &(const Bitset &b)const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=a[i]&b.a[i];
return ret;
}
Bitset operator |(const Bitset &b)const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=a[i]|b.a[i];
return ret;
}
Bitset operator ^(const Bitset &b)const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=a[i]^b.a[i];
return ret;
}
Bitset operator <<(const int t)const
{
Bitset ret;
unsigned last=0;
int high=t>>5,low=t&31;
for(int i=0;i+high<1600;i++)
{
ret.a[i+high]=last|(a[i]<<low);
if(low)last=a[i]>>(32-low);
}
return ret;
}
Bitset operator >>(const int t)const
{
Bitset ret;
unsigned last=0;
int high=t>>5,low=t&31;
for(int i=1600-1;i>=high;i--)
{
ret.a[i-high]=last|(a[i]>>low);
if(low)last=a[i]<<(32-low);
}
return ret;
}
vector<int> ones()const
{
vector<int> ret;
for(int i=0;i<1600;i++)
{
unsigned tmp=a[i];
while(tmp)
{
short t=__builtin_ctz(tmp);
ret.pb((i<<5)|t);
tmp^=1u<<t;
}
}
return ret;
}
}use,trans,cur;
|
