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;
}