线性基

Posted on | In | | Visitors:
Words count in article: 1.1k | Reading time ≈ 4

796456.jpg

线性基

线性基用于求解这样的问题：在n个数中选任意个数，求满足某个性质的异或和。
什么是线性基？线性基是一个数集，其中若干个数异或起来可以得到原数集中任何一个数。

性质

原数集中任意一个数都可以由线性基里面的一些数异或得到。
线性基里面任意个数异或起来都不等于0.
线性基里面数的个数唯一，且在保证前面性质的基础上个数最少。

构造

这里直接给出线性基的构造方法

1
2
3
4
5
6
7
8
9
10
11
void _insert(ll x) {
    //插入数x
    for (ll i = 60; ~i; --i) {
        if (!((x >> i) & 1))continue;
        if (base[i])x ^= base[i];
        else {
            base[i] = x;
            break;
        }
    }
}

问题求解

最大值

直接从高位到低位贪心，如果异或当前的线性基可以使得答案变大就异或。
即

1
2
3
4
5
6
7
ll getmax() {
    ll ans = 0;
    for (ll i = 50; ~i; --i)
        if ((ans ^ base[i]) > ans)
            ans ^= base[i];
    return ans;
}

为什么这样做是对的呢？考虑我们上面的构造过程，P[i]一定是考虑了更高位的线性基的，所以只要保证当前位会使答案增加即可，低位的总贡献无论如何都不会比一个高位的贡献大。

区间查询最大值

在求最大值的基础上，我们可以得到序列中求区间最大值的算法，该算法还支持动态扩大区间。
我们构造前缀线性基，即对每个位置i构造[1,i]的线性基，并且记录线性基上插入的数字的位置，保证这个位置尽量靠后。
更多实现细节看模板

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
void _insert(int x, int loc) {
	//做前缀线性基，先复制[1,loc-1]的，在这个基础上插入x
	for (int i = 0; i <= 31; ++i)
		base[loc][i] = base[loc - 1][i],
		pos[loc][i] = pos[loc - 1][i];
	for (int i = 31, now = loc; ~i; --i) {
		if (!(x >> i))continue;
		if (base[loc][i] == 0) {
			base[loc][i] = x;
			pos[loc][i] = now;
			break;
		}
		//pos记录线性基中插入的数在原序列的位置，尽量保留靠后的数
		//由于其中保留的数只可能是之前插入的，所以保存的位置不会超过loc
		if (now > pos[loc][i]) {
			swap(now, pos[loc][i]);
			swap(x, base[loc][i]);
		}
		x ^= base[loc][i];
	}
}
int query(int l, int r) {
	if (l > r)swap(l, r);
	int ans = 0;
	//最终查询的时候，只需要查看r处的线性基，由于前面我们保证了线性基中的数位置尽量靠后
	//所以只用看线性基中的数是否>=l即可
	for (int i = 31; ~i; --i) {
		if (pos[r][i] >= l && (base[r][i] ^ ans) > ans)
			ans ^= base[r][i];
	}
	return ans;
}

最小值

这个很显然。
如果是问线性基能异或出的最小值，那就是最小的base
如果是问原数集能异或出的最小值，那就再看看有没有数不能插入线性基，如果有，最小值就是0。

第k小值

在前面构造的线性基的基础上进行改进处理，使得每一位上的线性基最高位就是这一位。

1
2
3
4
5
6
7
8
9
10
void presolve() {
    for (ll i = 60; ~i; --i)
        for (int j = i + 1; j <= 60; ++j)
            if ((base[j] >> i) & 1)
                base[j] ^= base[i];
    tot = 0;
    for (int i = 0; i <= 60; ++i)
        if (base[i])
            base[tot++] = base[i];
}

查询的时候，就可以通过k的二进制来选择是否异或上某个线性基了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll query(int k) {
    //tot为线性基中插入的元素个数
    //如果插入元素比元素总数少，说明可以异或出0，特判一下
    if (k == 1 && (1ll << tot) < n)return 0;
    //线性基求解的是不为0的第k小，因此如果有0就应该求第k-1小
    if ((1ll << tot) < n)--k;
    ll ans = 0;
    for (ll i = 0; i <= 60; ++i)
        if (base[i]) {
            if (k & 1)ans ^= base[i];
            k >>= 1;
        }
    return ans;
}

判断一个数能否被线性基异或得出

尝试将这个数插入线性基，能插入说明不能，不能插入说明能。