线性基讲解

定义

设数集T的值域范围为[1,2^n−1]。
T的线性基是T的一个子集A={a1,a2,a3,...,an}。
A中元素互相xor所形成的异或集合，等价于原数集T的元素互相xor形成的异或集合。
可以理解为将原数集进行了压缩。

性质
1.设线性基的异或集合中不存在0。
2.线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。
3.线性基二进制最高位互不相同。
4.如果线性基是满的，它的异或集合为[1,2^n−1]。
5.线性基中元素互相异或，异或集合不变。

维护
插入
如果向线性基中插入数x，从高位到低位扫描它为1的二进制位。
扫描到第i时，如果ai不存在，就令ai=x否则x=x⊗ai。
x的结局是，要么被扔进线性基，要么经过一系列操作过后，变成了0。

 1 bool insert(long long val)
 2 {
 3     for (int i=60;i>=0;i--)
 4         if (val&(1LL<<i))
 5         {
 6             if (!a[i])
 7             {
 8                 a[i]=val;
 9                 break;
10             }
11             val^=a[i];
12         }
13     return val>0;
14 }

View Code

合并

将一个线性基暴力插入另一个线性基即可。

1 L_B merge(const L_B &n1,const L_B &n2)
2 {
3     L_B ret=n1;
4     for (int i=0;i<=60;i++)
5         if (n2.d[i])
6             ret.insert(n2.d[i]);
7     return ret;
8 }

View Code

查询

存在性

如果要查询 $x$

最大值

从高位到低位扫描线性基。
如果异或后可以使得答案变大，就异或到答案中去。

1 long long query_max()
2 {
3     long long ret=0;
4     for (int i=60;i>=0;i--)
5         if ((ret^d[i])>ret)
6             ret^=d[i];
7     return ret;
8 }

View Code

最小值

　　最小值即为最低位上的线性基。

1 long long query_min()
2 {
3     for (int i=0;i<=60;i++)
4         if (d[i])
5             return d[i];
6     return 0;
7 }

View Code

k小值
根据性质3。
我们要将线性基改造成每一位相互独立。
具体操作就是如果i<j，aj的第i位是1，就将aj异或上ai。
经过一系列操作之后，对于二进制的某一位i。只有ai的这一位是1，其他都是0。
所以查询的时候将k二进制拆分，对于1的位，就异或上对应的线性基。
最终得出的答案就是k小值。

 1 void rebuild()
 2 {
 3     for (int i=60;i>=0;i--)
 4         for (int j=i-1;j>=0;j--)
 5             if (d[i]&(1LL<<j))
 6                 d[i]^=d[j];
 7     for (int i=0;i<=60;i++)
 8         if (d[i])
 9             p[cnt++]=d[i];
10 }
11 long long kthquery(long long k)
12 {
13     int ret=0;
14     if (k>=(1LL<<cnt))
15         return -1;
16     for (int i=60;i>=0;i--)
17         if (k&(1LL<<i))
18             ret^=p[i];
19     return ret;
20 }

View Code

模板

 1 struct L_B{
 2     long long d[61],p[61];
 3     int cnt;
 4     L_B()
 5     {
 6         memset(d,0,sizeof(d));
 7         memset(p,0,sizeof(p));
 8         cnt=0;
 9     }
10     bool insert(long long val)
11     {
12         for (int i=60;i>=0;i--)
13             if (val&(1LL<<i))
14             {
15                 if (!d[i])
16                 {
17                     d[i]=val;
18                     break;
19                 }
20                 val^=d[i];
21             }
22         return val>0;
23     }
24     long long query_max()
25     {
26         long long ret=0;
27         for (int i=60;i>=0;i--)
28             if ((ret^d[i])>ret)
29                 ret^=d[i];
30         return ret;
31     }
32     long long query_min()
33     {
34         for (int i=0;i<=60;i++)
35             if (d[i])
36                 return d[i];
37         return 0;
38     }
39     void rebuild()
40     {
41         for (int i=60;i>=0;i--)
42             for (int j=i-1;j>=0;j--)
43                 if (d[i]&(1LL<<j))
44                     d[i]^=d[j];
45         for (int i=0;i<=60;i++)
46             if (d[i])
47                 p[cnt++]=d[i];
48     }
49     long long kthquery(long long k)
50     {
51         int ret=0;
52         if (k>=(1LL<<cnt))
53             return -1;
54         for (int i=60;i>=0;i--)
55             if (k&(1LL<<i))
56                 ret^=p[i];
57         return ret;
58     }
59 }
60 L_B merge(const L_B &n1,const L_B &n2)
61 {
62     L_B ret=n1;
63     for (int i=60;i>=0;i--)
64         if (n2.d[i])
65             ret.insert(n1.d[i]);
66     return ret;
67 }

View Code