线性基简单运用

一、简介

(存在观点认为,线性基不是数据结构。反正我觉得它挺数据结构的。)

二、功能

1.构造

1
2
3
4
5
6
7
8
bool insert(int x){
    for(int i=60;i>=0;--i)
      if(x&(1ll<<i)){
        if(!w[i]) {w[i]=x;return true;}
    else x^=w[i];
      }
    return false;
}
2.求最大值 (P3812 【模板】线性基)

1
2
3
4
5
6
7
int get_max(){
    int ans=0;
    for(int i=60;i>=0;--i)
    if((ans&(1ll<<i))==0)
      ans^=w[i];
    return ans;
}
3.求种类数(P3857 [TJOI2008]彩灯 )

1
2
3
int get_tpye(){
    return 1ll<<siz;
}

三、简单的全局线性基问题

1.n个数选择中选择若干个数使得[没选到的数的任意子集异或和不为0]且[选到的数之和最小]  P4301 [CQOI2013] 新Nim游戏 

从[没选到的数的任意子集异或和不为0]这个要求很容易看出要用线性基,要满足第二个条件则需要一点简单小技巧。

2.已知一个序列a,计数满足[每一个位置的数pi  为  a序列的真前缀子集 和 ai 的 异或和]新序列p  T224316 A. 45吨主战坦克【省选计划 · 模拟赛 #1】

ans=π 2^|vi|,vi为每一个前缀的线性基的大小。

3.无向连通图(n<=5e4,m<=1e5),求从一号节点到n号节点的最大异或和路径。P4151 [WC2011]最大XOR和路径 

同样很容易想到可能要用线性基。

但是具体要怎么用呢?

对于神奇的题目,有时可能样例会体现出一些可以通向正解的特征

(经典样例题:P3747 [六省联考 2017] 相逢是问候 )

于是我们看一下样例

这个路径很明显可以分为两部分

①1→2→4→3→5,这是一条从起点到终点的路径

②5→2→4→5,这是一个环

先看①,很显然为了满足题目要求,最后的路径子集一定有从起点到终点的路径(具体选哪一个还不知道,先放着)

再看②,这是一个环。我们发现可以构造路径使得[答案 与 环的异或和 异或]。每一个环的异或和都可以加入到对答案可能产生贡献的线性基中。

我们考虑一下②的这个结论有没有什么用处。可以想到答案的形式无非就两种,一种是一条[简单路径],另一种是[简单路径+环+简单路径+环……]

有了这个结论,我们可以统一答案为[简单路径]+[由环异或和构成的线性基]

接下来考虑最优简单路径怎么选。这个无非也就两种:一个简单→直接选,多个简单路径→任选一条简单路径经过[由环异或和构成的线性基]之后就会变成最优简单路径(对于可能出现的环套环现象也可以通过环的异或得到最优情况)。

至此,先求出所有的环,然后找一条路径丢到线性基走一遍,本题结束。

4.线段树分治上询问两点间最短异或路径(n,m,q<2e5)(CF938G Shortest Path Queries)

在线段树的每个节点上放线性基。

每次询问在生成树上log找出一条路径丢到线性基里就可以了

四、简单的局部线性基问题,线性基的后偏构造(前缀线性基)

其实也不是什么高端东西,就是线性基中选的数贪心一下。

考虑原本的线性基构造方法(可参考上方代码),可以一个性质:

    [发现选出来的数一定是最前面符合条件的若干个数。]

于是可以通过对构造方法的改动,可以得到一些新性质的线性筛

比如这样


1
2
3
4
5
6
7
8
9
bool insert(int x){
    bool _end=false;
    for(int i=60;i>=0;--i)
    if(x&(1ll<<i)){
        if(!w[i]) {w[i]=x;return true;}
        else {swap(x,w[i]);_end=true;}
    }
    return _end;
}

这样线性基里面的性质就是

    [发现选出来的数一定是最后面符合条件的若干个数。]

可以通过记录位置等方式,处理区间型异或和最大值问题。

1.求区间异或和最大值 CF1100F Ivan and Burgers 
2.求树上异或和最大值 P3292 [SCOI2016]幸运数字 

此题两种比较普通的做法:

①这是一个维护[具有无前/后效性性质]的树上路径问题

可以用LCA直接过

②经典类差分思想:

树上差分:f(u,v)=f(rt,u)+f(rt,v)-f(rt,lca)-f(rt,fa[lca])

本题:预处理出根节点到所有节点的后偏线性基,询问时合并u,v两个节点内比lca深的有效部分即可。