真·浅谈线性基

或许是该努努力了呢，快要来不及了。

异或线性基

简单来说，线性基是一个数的集合，每个序列都拥有一个线性基，线性基中的若干个数异或起来原序列中的任意一个数。

重要性质：

1. 原序列中的任意一个数都能通过线性基中的若干个数异或得到。
2. 线性基内任意数异或和不为 $0$。
3. 一个序列的所有线性基大小相同。

别的性质：

4. 由 $n$ 个数组成的大小为 $s$ 的线性基，能构成 $2^s$ 种不同的数，每个数出现 $2^{n-s}$ 次。

基本操作

插入

1
2
3
4
5
6
7
8
9
10

void insert(int x){
    for(int k=62;~k;k--)
        if((x>>k)&1){
            if(!d[k]){
                d[k] = x;
                break;
            }
            x ^= d[k];
        }
}

求异或最大值

1
2
3
4
5
6

int query(int x=0){
    for(int k=62;~k;k--)
        if((x^d[k])>x)
            x ^= d[k];
    return x;
}

求异或最小值

如果是序列内部最小的异或值，那么如果有元素不能被插入线性基，最小值为 $0$，否则为线性基中最小的元素。

如果是丢一个数进去的话，类似于求异或最大值做就行了。

查询存在性

能插入进去就是不存在，否则就是存在。

求 $k$ 小值

先预处理，对于线性基 $d$，如果 $d_i(0 \leq i < n)$ 的二进制位 $j(0 \leq j < i)$ 为 $i$，$d_i$ 异或上 $d_j$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void init(){
    for(int k=0;k<62;k++)
        for(int j=0;j<k;j++)
            if((d[k]>>j)&1)
                d[k] ^= d[j];
}

int kth(int K){
    if(s<n)
        K--;
    //n 表示序列长度，s 表示线性基元素个数
    int ans = 0;
    for(int k=0;k<62;k++)
        if((K>>k)&1)
            ans ^= d[k];
    return ans;
}

线性基求并

把一个线性基的全部元素插入另一个就行。

例题

P3857 [TJOI2008] 彩灯

一个序列若干数异或得到的集合和这个序列的线性基异或得到的集合是一样的。

由于线性基性质 2，一个大小为 $s$ 的线性基能异或得到 $2^s$ 个数。

那么算出这个序列的线性基，答案就为 $2^s$。

P4570 [BJWC2011] 元素

因为线性基性质 2，线性基内任意数异或和不为 $0$，考虑线性基。

因为线性基性质 3，无论顺序能放进去的总个数是不变的，贪心的先放贡献大的就行。

P5556 圣剑护符

距离 $>30$ 的路径是一定存在一个子集异或值为 $0$ 的，因为这样线性基一定会被插满。

那么对于 $\leq 30$ 的暴力用线性基判断，用树剖和线段树维护 lca 和修改。

P4151 [WC2011] 最大XOR和路径

走的路径一定是一条链然后走到了一些别的地方又回来。

一个路径走两遍就没了贡献，那么有贡献的一定是走到了环，并且贡献为环本身，因为走去环回来这条路径被走了两遍。

这样的话所有的环都能自由选择，把所有的小环的异或值加入线性基（大环相当于小环的异或值），就相当于自由选择所有的环。

考虑选择走的 $1\rightarrow n$ 链，链可以随便选，因为如果有多条链，一定都构成了环，那么选择构成的那个环就相当于选择了另一条链。

把选择的链的异或值去线性基里跑最大异或值就行了。CF845G 就是跑最小值。

P5607 [Ynoi2013] 无力回天 NOI2017

首先这是个数据结构套线性基础，考虑线段树，但是修改是区间修改线性基不太好做。

差分，$b_i=a_i\ \text{xor}\ a_i$，把区间修改变为单点修改。

$a_i$ 可以用 $b_1\ \text{xor}\ b_2 \dots \ \text{xor}\ b_i$ 表示出来，那么 $a_l\dots a_r$ 的所以子集异或都能用 $a_l\ b_{l+1} \ldots b_r$ 表示出来。

用线段树维护 $b$ 的线性基，同时用树状数组维护 $b$ 的前缀异或和来求 $a_l$。

询问就求出 $b_{l+1}\dots b_r$ 插入 $a_l$ 然后求异或最大值，特判 $l=r$。

线性基合并的复杂度为 $O(\log^2V)$，所以总复杂度为 $O(n \log n \log^2 V)$。

P3292 [SCOI2016] 幸运数字

因为是算异或最大值，求的是树上路径线性基，倍增直接做是 $\log m \log^2 V$ 的。

发现 线性基重复部分没有贡献，类似于 $\max,\gcd$ 这些，然后直接用 st 表那种做法做。

具体的，先倍增预处理线性基。对于询问找到 lca 之后拆成 $x \rightarrow lca$ 和 $y \rightarrow lca$ 两条链。对于一条链 $x\rightarrow y$，倍增找到 $u$ 使得 $dep_u-dep_y+1=2^{\lfloor \log({dep_x-dep_y+1}) \rfloor-1}$，复杂度瓶颈在于合并线性基的 $O(\log^V)$，找 $u$ 的 $O(\log n)$ 无所谓。

复杂度为 $O(n \log^2 V+n \log^3 n)$，$n$ 比 $V$ 小足以通过。

P4869 albus就是要第一个出场

由 $n$ 个数组成的大小为 $s$ 的线性基，能构成 $2^s$ 种不同的数，每个数出现 $2^{n-s}$ 次。

查询排名就是从低位到高位看，如果第 $i$ 位存在线性基且查询的数 $q$ 二进制的第 $i$ 为 $1$，记 $c$ 为 $[0,i)$ 的线性基个数，排名加上 $2^c$。

因为是第 $i$ 位存在线性基，相当于强制选了第 $i$ 位，这样就不会算重。

不会证明，之后再补吧。