给出几个数,让您从中任选几个数使得它们的异或和最大,或者求出第 K 小异或和。这就需要线性基来处理。

引入

线性基就是一个容器。我们设这个容器为 $P$,则 $P_i$ 记录二进制最高位 $1$ 在第 $i$ 位的数。显然,线性基大小应该是 $\log_2N_{max}$ 的(因为需要记录二进制的每一位)。

基本操作

插入

让我们给出一组数,从前往后扫。对于每一个数,我们找出它二进制最高位 $1$ 所在的位置(暴力从最高位枚举即可),如果该位置对应的线性基为空,就插入这个数;如果不为空,则把这个数异或线性基上的数($x = x \oplus P_i$)继续找,直到找到能够插入的位置为止。

$x$ 最终会被插入到线性基中,或者没有插入最终变成 $0$ 。

举个栗子
给出这列数。

23 9 10 12 5

它们的二进制形式和二进制最高位 1 所在二进制位分别是

23:10111    4
9:1001      3
2:10        1
12:1100     3
5:101       2

那让我们把它们插入线性基。

23 -> p[4]
9 -> p[3]
2 -> p[1]
12 ^ 9 = 5 -> p[2]
5 ^ 5 = 0 不插入线性基

最终得到的线性基 $P_4\dots P_0$ 分别为 $23,9,5,2,0$。
其二进制形式长这样 (是不是非常整齐呢)

4:10111
3:-1001
2:--101
1:---10
0:-----

代码
maxL 指的是最高的二进制位。如 long long 类型是 64 位整型,则最高位是第 62 位(0~63位,其中有一个是符号位),所以从第 62 位开始枚举即可。

void ins(long long x) {
    for (int i = maxL; i >= 0; i--)
        if (x & (1LL << i)) {
            if (!p[i]) {
                p[i] = x;
                return;
            }
            x ^= p[i];
        }
}

合并线性基

暴力插入即可。(如果为空则插入,如果不为空就跳过)

线性基查询

查询最大异或和

我们从线性基的最高位开始枚举。显然越高位为 1 则异或和最大,所以可以采用一种贪心策略。

for (int i = maxL; i >= 0; i--)
    ans = max(ans, ans ^ p[i]);

看到这里你就可以做出这道模板题了。

查询最小异或和

从线性基最低位枚举即可。线性基最低位上的数即为结果。

查询某个数是否可以异或得到

从高位到低位扫描。类似于插入操作只不过不进行插入。

如果第 $i$ 位为 1,且该位对应的线性基不为空,则异或线性基上的数($x = x \oplus P_i$)继续扫描。
如果最后这个数变成了 0,则说明可以。

查询第 K 小异或和

再来一个数组来进行操作,将原来的线性基进行重新构造。

依然是从高位到低位枚举。若 $j < i$,当第 $i$ 位线性基存在且该线性基上的数第 $j$ 位为 1 时,就把 $P_i$ 异或上 $P_j$($P_i = P_i\oplus P_j$)。

这样处理之后线性基每一位都相互独立了,大概长这样

还是这列数 23 9 10 12 5
4:10001    17
3:-1001     9
2:--101     5
1:---11     3
0:-----     0

最后从低位到高位扫描一下进行上述处理后的线性基,如果该位的线性基存在,则加入到新的数组中。

最后求第 K 大时只需要从高位到低位枚举,如果 K 的第 $i$ 位为 1,则让 $ans$ 异或新数组的第 $i$ 位。($ans$ 初始值为 $0$)。

代码

long long query_kth(int k) {
    long long tmp[maxL + 3], ans = 0, cnt = 0;
    for (int i = maxL; i >= 0; i--)
        for (int j = i - 1; j >= 0; j--)
            if (p[i] & (1LL << j)) p[i] ^= p[j];
    for (int i = 0; i <= maxL; i++)
        if (p[i]) tmp[cnt++] = p[i];
    if (k >= (1LL << cnt)) return -1;
    for (int i = maxL; i >= 0; i--)
        if (k & (1LL << i)) ans ^= tmp[i];
    return ans;
}
分类: 知识

发表评论

邮箱地址不会被公开。 必填项已用*标注