线性基(洛谷3812)

线性基是一种解决异或相关问题的算法。

感谢 mwh 与我分享关于线性基的理解,让我了解线性基。

概念

线性基理论上来说是一种贪心的思路。一般情况下,我们需要从(二进制)高位到低位贪心,然而这样可能会产生其他影响(例如当前数的选择与否会影响到之前已选择的数)。线性基就巧妙的解决了这个问题。

假设我们已经有了一个集合 $S$ ,集合中有一数为 $P$ ,现在我们需要插入 $X$ ,则插入 $X$ 和插入 $ X xor P $ 是等价的,理性证明:

假设集合 $S$ 中任意个数其中包含 $P$ 的异或和的集合为 $S1$ ,不包含 $P$ 的为 $S2$ 。则插入 $X$ 后的 $S$ 中任意数的异或和集合 $S’ = X xor S1 + X xor S2$ ;插入 $X xor P$ 后 $S$ 中任意数的异或集合 $S’’ = (X xor P) xor S1 + (X xor P) xor S2 = X xor (P xor S1) + X xor (P xor S2) = X xor S2 + X xor S1$ 。所以 $S’ = S’’$ 插入 $X$ 和插入 $X xor P$ 等价,证毕。

实现

我们考虑维护一个集合SS[i]表示(二进制)最高位是 1 的某个数,这样的数在集合中有且仅有一个。

枚举a[1...n]中的每一个数字:

  1. 假设当前数字的最高位为 j
  2. 如果S[j]为空,则S[j] = a[i],退出
  3. 如果S[j]不为空,则a[i] xor= S[j],回到 1

这样对于每个a[i],只可能插入到S中一次,如果没有插入,则a[i]将会变成 0 ,异或 0 是没有意义的,可以直接省略。

接下来对于 S ,我们只需要前面所说的贪心即可。

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll read() {
ll x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 60;
int n;
ll ans;
ll _2[maxn], a[maxn], f[maxn];

int main() {

n = read();
for (int i = 1; i <= n; i++)
a[i] = read();
_2[0] = 1;
for (int i = 1; i <= 50; i++)
_2[i] = _2[i - 1] << 1;

for (int i = 1; i <= n; i++)
for (int j = 50; j >= 0; j--)
if (a[i] & _2[j]) {
if (f[j]) a[i] xor= f[j];
else {
f[j] = a[i];
break;
}
}
for (int j = 50; j >= 0; j--)
if ((ans & _2[j]) == 0) {
ans xor= f[j];
}

printf("%lld\n", ans);

return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×