0%

线性基

线性基的构造

线性基是怎么构造的?

大概就是考虑每个数 $a$,从高位到低位枚举,找到在线性基 $b$ 中没出现过的 $a$ 的最高位 $i$,将 $a$ 加入到线性基$b[i]$中,高于 $i$ 的 $a$ 的二进制位用线性基中的数给异或掉(因此此时 $i$ 就是 $a$ 的最高位了)。然后用类似高斯消元的方法,先用下面的行消自己,再用自己消上面的行,把线性基消成一个上三角矩阵。

线性基的性质

  • 线性基中所有向量线性无关,也就是不能异或出 0(废话
  • 线性基中每个对角线元素为 1 的列其余元素都为 0
  • 若线性基中向量个数 $m <n$,那么存在向量组线性相关,可以异或出 0,总的异或和的个数为
    $2^m$;否则,异或和个数为 $2^m - 1$
  • 若线性基中向量个数 $m$,那么线性基中每个向量在原集合的异或和中出现的次数为 $2^{n-m}$

题目

最大异或和

将线性基中所有数异或起来即可。

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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fl first
#define fr second
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 100000 + 5;

int n;
LL a[N], b[N];

void Calc()
{
for (int i = 1; i <= n; i++)
for (int j = 50; j >= 0; j--)
if ((1LL << j) & a[i])
{
if (b[j]) a[i] ^= b[j];
else
{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--)
if ((1LL << k) & b[j]) b[j] ^= b[k];
for (int k = j + 1; k <= 50; k++)
if ((1LL << j) & b[k]) b[k] ^= b[j];
break;
}
}
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
Calc();
LL ans = 0;
for (int i = 0; i <= 50; i++) ans ^= b[i];
printf("%lld\n", ans);
return 0;
}

k 大异或和

在线性基中找 $k$ 对应的二进制的异或和。

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
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fl first
#define fr second
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 100000 + 5;

int n, cnt;
LL a[N], b[100];
vector<LL> base;

void Calc()
{
for (int i = 1; i <= n; i++)
for (int j = 60; j >= 0; j--)
if ((a[i] >> j) & 1)
{
if (b[j]) a[i] ^= b[j];
else
{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--)
if ((b[j] >> k) & 1) b[j] ^= b[k];
for (int k = j + 1; k <= 60; k++)
if ((b[k] >> j) & 1) b[k] ^= b[j];
break;
}
}
for (int i = 0; i <= 60; i++)
if (b[i]) base.pb(b[i]);
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
Calc();
int m;
scanf("%d", &m);
while (m--)
{
LL k;
scanf("%lld", &k);
LL ans = 0;
if (base.size() != n) k--;
if (k >= (1LL << base.size()))
{
puts("-1");
continue;
}
for (int i = 0; i < base.size(); i++)
if ((k >> i) & 1) ans ^= base[i];
printf("%lld\n", ans);
}
return 0;
}

「WC2011」最大XOR和路径

结论:1 - n 的最大异或和路径,可以由任意 1 - n 异或和路径与图上一些环的异或得到。

挺显然的。。就是不会严格证明。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fl first
#define fr second
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 50000 + 5;
const int M = 100000 + 5;

int n, m, tot, head[N], to[M * 2], nxt[M * 2], vis[N];
LL cost[M * 2], sum[N], b[100];

vector<LL> a, base;

void Add(int u, int v, LL e)
{
nxt[++tot] = head[u], head[u] = tot, to[tot] = v, cost[tot] = e;
}

void DFS(int u, LL now)
{
vis[u] = 1;
sum[u] = now;
for (int e = head[u]; e; e = nxt[e])
{
int v = to[e];
if (!vis[v]) DFS(v, now ^ cost[e]);
else a.pb(sum[v] ^ sum[u] ^ cost[e]);
}
}

void Calc()
{
for (int i = 0; i < a.size(); i++)
for (int j = 60; j >= 0; j--)
if ((a[i] >> j) & 1)
{
if (b[j]) a[i] ^= b[j];
else
{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--)
if ((b[j] >> k) & 1) b[j] ^= b[k];
for (int k = j + 1; k <= 60; k++)
if ((b[k] >> j) & 1) b[k] ^= b[j];
break;
}
}
for (int i = 0; i <= 60; i++)
if (b[i]) base.pb(b[i]);
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
LL w;
scanf("%d%d%lld", &u, &v, &w);
Add(u, v, w);
Add(v, u, w);
}
DFS(1, 0);
Calc();
LL res = sum[n];
for (int i = base.size() - 1; i >= 0; i--)
if ((res ^ base[i]) > res) res ^= base[i];
printf("%lld\n", res);
return 0;
}

「HDU 6579」 Operation - 线性基

操作:在序列后面加入一个数、询问一个区间最大异或子序列,强制在线。

维护以每个位置结尾的线性基,再维护线性基中每一位的最右端点。插入时,尽量放右端点大的,然后将其他位向后移。查询时,在以 $r$ 结尾线性基中,用最右端点大于等于 $l$ 的更新答案。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fl first
#define fr second
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 1000000 + 5;

int n, m, a[N], b[N][31], pos[N][31];

void Insert(int now, int x)
{
int p = now;
for (int i = 0; i <= 30; i++) b[p][i] = b[p - 1][i], pos[p][i] = pos[p - 1][i];
for (int i = 30; i >= 0; i--)
if ((x >> i) & 1)
{
if (!b[p][i])
{
b[p][i] = x, pos[p][i] = now;
break;
}
if (pos[p][i] < now)
swap(pos[p][i], now), swap(b[p][i], x);
x ^= b[p][i];
}
}

int Query(int l, int r)
{
int ans = 0;
for (int i = 30; i >= 0; i--)
if (pos[r][i] >= l)
ans = max(ans, ans ^ b[r][i]);
return ans;
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
Insert(i, a[i]);
}
int ans = 0, cnt = n;
for (int i = 1; i <= m; i++)
{
int op;
scanf("%d", &op);
if (op == 0)
{
int l, r;
scanf("%d%d", &l, &r);
l = (l ^ ans) % cnt + 1, r = (r ^ ans) % cnt + 1;
if (l > r) swap(l, r);
ans = Query(l, r);
printf("%d\n", ans);
}
else
{
int x;
scanf("%d", &x);
x ^= ans;
Insert(++cnt, x);
}
}
}
return 0;
}