关于整型异或的线性基

发表于 更新于 分类于

$\ \ \ \ \ \ \ \,$关于线性基的复习笔记：

$\ \ \ \ \ \ \,$基（$\tt basis$）是线性代数中的一个概念，它是描述、刻画向量空间的基本工具。而在现行的 OI 题目中，通常在利用基在异或空间中的一些特殊性质来解决题目，而这一类题目所涉及的知识点被称作线性基。

$\ \ \ \ \ \ \,$具体证明先不谈，【给个链接】，下面主要讲关于整型异或的线性基的代码实现和操作。

$\ \ \ \ \ \ \,$简单来说，线性基是解决一系列整形集合异或值的轻量数据结构，主要思想在于贪心，空间复杂度很低，只有$\log n$的级别（$n$为元素大小上界）:

1
2
3
4
struct Linear_Base{
  long long a[Lim+10];
}LB;

$\ \ \ \ \ \ \,$他支持的操作有（$n$为元素大小上界）：

  1. 向集合中插入一个整形元素（$O(\log n)$）

  2. 询问集合的中元素是否可以相互异或出某个整形（$O(\log n)$）

  3. 询问集合的中元素与某个整形可以相互异或出的最大值（$O(\log n)$）

  4. 询问集合的中元素与某个整形可以相互异或出的最小值（$O(\log n)$）

  5. 询问集合的中元素可以相互异或出的第$k$大值（$O(\log^2 n)$）

  6. 合并两个集合(线性基)（$O(\log^2 n)$）

插入

$\ \ \ \ \ \ \,$考虑按位异或其实只与每一个位数有关，并且要这个位数为$1$的时候才会造成贡献。问题是如何用 $\log n$ 的空间来描述整个集合的异或集合，我们的想法是：

  • 如果这个数前面高数位的值可以被已有集合表达，那么我们用插入的数异或掉这个可以表达的数，就可以把插入的数化为低位。

  • 如果这个数前面高数位的值不能被已有集合表达，那么我们就顺势插入集合，然后弹出。

$\ \ \ \ \ \ \,$这样我们就可以保证，集合的异或值都可以表达出来，没有遗漏，代码如下：

1
2
3
4
5
6
void insert(long long x){
  for(int i=Lim;i>=0;i--)if(x&(1ll<<i)){
    if(!a[i]){a[i]=x;return;}
    else x^=a[i];
  }
}

查询是否存在

$\ \ \ \ \ \ \,$在插入完成后，线性基的每一一个位置存放的都是这个集合可以通过异或表达的元素，并且最高位就是这个数位，于是查询存在就边成了：

  • 如果询问的数在这个数位为$1$,那么要表达询问的数的一个元素，肯定是这个位数上的元素，于是我们拿询问的数去异或他，询问的数将会成功减少至少一个数位。

  • 如果询问的数在这个数位为$0$,那么要表达询问的数的元素肯定没有这个位数上的元素，不然后面再怎么异或，这个位数就消不掉了，所以直接跳过这种位数。

$\ \ \ \ \ \ \,$当然了，要是最后把要查询的这个数都异或为$0$了,这个数当然就存在了，若是异或到后面的位数上的元素都是空的了还没有归$0$，那么肯定就不存在了，代码如下：

1
2
3
4
5
6
7
bool check(long long x){
  for(int i=Lim;i>=0;i--)if(x&(1ll<<i)){
    if(!a[i])break;
    x^=a[i];
  }
  return x>0;
}

查询最大

$\ \ \ \ \ \ \,$这个比较好想，我们依然从高位到地位枚举，若是询问的数这一个数位的元素异或起来变大了，那么就异或起来，最后便可以得到答案：

1
2
3
4
5
long long querymax(long long res){
  for(int i=Lim;i>=0;i--)
  if((res^a[i])>res)res^=a[i];
  return res;
}

查询最小

$\ \ \ \ \ \ \,$查询最小的话，我们的策略就需要改变一下了，应该是尽量把为搞数位降成低数位，那么我们的操作和插入的操作其实差不多：

1
2
3
4
5
long long querymax(long long res){
  for(int i=Lim;i>=0;i--)
  if(res&(1ll<<i))res^=a[i];
  return res;
}

查询组合第$k$大

$\ \ \ \ \ \ \,$这个是最复杂的操作了，简单说一下就好了，主要记板子，主要的想法是我们需要将每一位数的元素后面的位数也消掉，那么我们每一数位的元素就差不多变成了$2^i$，然后把$k$位数拆分就好了：

1
2
3
4
5
6
7
8
9
long long querykth(int k){
  long long tmp[Lim+10],res=0,cnt=0;
  for(int i=0;i<=Lim;i++){
    for(int j=i-1;j>=0;j--)if(a[i]&(1ll<<j))a[i]^=a[j];
    if(a[i])tmp[cnt++]=a[i];
  }
  for(int i=0;i<cnt;i++)if(k&(1ll<<i))res^=tmp[i];
  return res;
}

合并

$\ \ \ \ \ \ \,$合并的话，就是把一个线性基里面整合的元素再插入另一个就好了呗：

1
2
void merge(const Linear_Base &other)
{for(int i=0;i<=Lim;i++) insert(other.a[i]);}

完整模板代码：

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
struct Linear_Base{
  long long a[Lim+10];
  void insert(long long x){
    for(int i=Lim;i>=0;i--)if(x&(1ll<<i)){
      if(!a[i]){a[i]=x;return;}
      else x^=a[i];
    }
  }
  bool check(long long x){
    for(int i=Lim;i>=0;i--)if(x&(1ll<<i)){
      if(!a[i])break;
      x^=a[i];
    }
    return x>0;
  }
  long long querymax(long long res){
    for(int i=Lim;i>=0;i--)if((res^a[i])>res)res^=a[i];
    return res;
  }
  long long querymin(long long res){
    for(int i=Lim;i>=0;i--)if(res&(1ll<<i))res^=a[i];
    return res;
  }
  long long querykth(int k){
    long long tmp[Lim+10],res=0,cnt=0;
    for(int i=0;i<=Lim;i++){
      for(int j=i-1;j>=0;j--)if(a[i]&(1ll<<j))a[i]^=a[j];
      if(a[i])tmp[cnt++]=a[i];
    }
    for(int i=0;i<cnt;i++)if(k&(1ll<<i))res^=tmp[i];
    return res;
  }
  void merge(const Linear_Base &other)
  {for(int i=0;i<=Lim;i++) insert(other.a[i]);}
}LB;