CodeNote

「CodeNote」 线性基

Posted by Dawn-K's Blog on September 14, 2019

线性基

参考资料

参考资料2

模板来源

概述

线性基是一种擅长处理异或问题的数据结构.设值域为[1,$N$]，就可以用一个长度为$\lceil \log_2N \rceil$的数组来描述一个线性基。特别地，线性基第$i$位上的数二进制下最高位也为第$i$位。

性质

  1. 原序列里面的任意一个数都可以由线性基里面的一些数异或得到(也能异或得到一些不存在于集合的数)
  2. 线性基里面的任意一些数异或起来都不能得到0
  3. 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

注意:性质1还有另一种说法:通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。

插入(初始化)

初始化即是将逐个元素插入线性基的过程.

由线性基的定义可知,一位上只有一个数字

我们考虑插入的操作，令插入的数为$x$，考虑x的二进制最高位$i$，

  • 若线性基的第$i$位为0，则直接在该位插入$x$，退出；
  • 若线性基的第$i$位已经有值$a_i$，则$x = x\oplus a_i$，重复以上操作直到$x=0$。

如果退出时$x=0$，则此时线性基已经可以表示原先的$x$了；反之，则说明为了表示$x$，往线性基中加入了一个新元素。

1
2
3
4
5
6
7
8
9
10
11
12

void add(ll x) {
    for (int i = 50; i >= 0; --i) {  
        if (x & (1LL << i)) { // x的最高位是1
            if (d[i]) {  // 当前位置已经有线性基元素了,所以就异或一下
                x ^= d[i];
            } else {  // 当前位置没有,就插入x,然后退出
                d[i] = x;
                break;
            }
        }
    }
}

验证

无法插入即不可表示.

1
2
3
4
5
6
7
8
9
10
11
12

bool check(ll x) {
    for (int i = 50; i >= 0; --i) {
        if (x & (1LL << i)) { // //注意，如果i大于31，前面的1的后面一定要加ll
            if (d[i]) { // 如果此位上已有元素,则异或一下
                x ^= d[i];
            } else { // 如果没有,则说明无法构成
                return false;
            }
        }
    }
    return true; // 可以构成
}

查询异或最小值

查询最小值相对简单一些.我们不难发现,在线性基的元素中,每个元素的最高位都是不同的(不会有两个线性基的元素的最高位相同).所以线性基中最小的元素,只要与其他元素异或,所得的结果必然比其本身大,因此,异或的最小值就是线性基的最小值(此处关于0的问题,看下文查询第k小.

查询异或最大值

这个算法相对固定.因为线性基中所有元素的最高位都不相同,所以可以从高到低逐步贪心获得.

1
2
3
4
5
6
7
8
9

ll cal() {
    ll ans = 0;
    for (int i = 50; i >= 0; --i) {
        if ((ans ^ d[i]) > ans) { // 只要能更新结果就更新
            ans = ans ^ d[i];
        }
    }
    return ans;
}

查询第k小

完整的说，应该是——从一个序列中取任意个元素进行异或，求能异或出的所有数字中第k小的那个。

这里就出现了一个问题.如果说原集合的元素个数是N,线性基的个数也是N,那么就一定无法凑出0,也就是线性基的最小值不是0,而是线性基中的最小值.

如果线性基的元素个数(下文称tot)小于N,那么最小值就是0.

在解决这个问题之前,我们对线性基进行一些预处理.我们将线性基元素都转化为形如$2^i$的形式,

1
2
3
4
5
6
7
8
9
10

void work()//处理线性基
{
    for (int i = 0; i <= 50; i++) {
        for (int j = 0; j < i; j++) {
            if (d[i] & (1ll << (j))) {
                d[i] ^= d[j];
            }
        }
    }
}

模板

能力有限,未能把它改成适合int的形式,有时间再进行更新.

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
78
79
80
81
82
83
84
85
86
87
88

const int ks = 31; // 切记,如果Type是ll,那么此处一定是63,是其他的可能会wa
typedef ll Type;
Type t1[ks + 1], t2[ks + 1];//线性基求交 临时数组
#define inf 0x3f3f3f3f
struct LinearBasis {
    Type v[ks + 1];//线性基
    Type p[ks + 1], temp[ks + 1], num = 0, flag;//求第k大数据
    int n = 0;
 
    LinearBasis() {
        memset(v, 0, sizeof(v));
    }
 
    void insert(ll x)//将x插入线性基v中
    {
        n++;
        for (int j = ks; j >= 0; j--)
            if ((x >> j) & 1)
                if (!v[j]) {
                    v[j] = x;
                    break;
                } else x ^= v[j];
        flag = 0;
    }
 
    void BaseInter(LinearBasis &v1, LinearBasis &v2)//将v1和v2求交，存入v
    {
        for (int i = 0; i <= ks; i++) t1[i] = t2[i] = v1.v[i];
        for (int i = 0; i <= ks; i++) {
            ll x = v2.v[i], t = 0;
            if (!x) continue;
            int j = i;
            for (; j >= 0; j--)
                if (x & (1 << j)) {
                    if (t1[j]) x ^= t1[j], t ^= t2[j];
                    else break;
                }
            if (!x) v[i] = t;
            else t1[j] = x, t2[j] = t;
        }
    }
 
    Type getmax()//获取最大值
    {
        Type ans = 0;
        for (int i = ks; i >= 0; i--) {
            ans = max(ans, ans ^ v[i]);
        }
        return ans;
    }
 
 
    ll Kth(ll k)//求第k大
    {
        if (!flag) {//如果没初始化过
            for (int i = 0; i <= ks; i++)
                p[i] = v[i];
            for (int i = 0; i <= ks; i++)
                for (int j = 0; j < i; j++)
                    if (p[i] & (1LL << j))
                        p[i] ^= p[j];
            for (int i = 0; i <= ks; i++) {
                if (p[i]) temp[num++] = p[i];
            }
            flag = 1;
        }
 
        if (n != num)//如果能构成异或为0
            k--;
        if (k >= (1LL << num)) {//如果超过 2^num-1个，则不能构成
            return -1;
        } else {
            ll ans = 0;
            for (int i = 0; i < num; i++) {//构成第k个数
                if (k & (1LL << i))
                    ans ^= temp[i];
            }
            return ans;
        }
    }
 
    bool check(ll x)//检查x是否能被线性基v表示
    {
        for (int i = ks; i >= 0; i--)
            if ((x >> i) & 1) x ^= v[i];
        return x == 0;
    }
};

应用

19牛客第四场B

2019牛客多校第四场B

题意

给你N个集合,然后m组询问.每次询问给出三个整数,l,r,x. 如果任意$i \in [l,r]$ ,i号集合可以表示出(此处是指可以通过元素之间的异或来得到)x,那么输出”YES”,否则输出”NO”.

分析

需要补充一个”交”的性质.如果x能被$A∩B$表示,那么就一定是既能被A 表示又能被B表示.而且这个性质还可以继续延伸,这一点就可以被线段树利用做区间判断了.

所以这个题就是线性基+线段树.

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned int uint;
#define lc (o << 1)
#define rc (o << 1 | 1)
#define mid (l + r >> 1)
int n, m;
const int ks = 63;
typedef long long ll;
typedef ll Type;
Type t1[ks + 1], t2[ks + 1];//线性基求交 临时数组
 
struct LinearBasis {
    Type v[ks + 1];//线性基
    Type p[ks + 1], temp[ks + 1], num = 0, flag;//求第k大数据
    int n = 0;
 
    LinearBasis() {
        memset(v, 0, sizeof(v));
    }
 
    void insert(ll x)//将x插入线性基v中
    {
        n++;
        for (int j = ks; j >= 0; j--)
            if ((x >> j) & 1)
                if (!v[j]) {
                    v[j] = x;
                    break;
                } else x ^= v[j];
        flag = 0;
    }
 
    void BaseInter(LinearBasis &v1, LinearBasis &v2)//将v1和v2求交，存入v
    {
        for (int i = 0; i <= ks; i++) t1[i] = t2[i] = v1.v[i];
        for (int i = 0; i <= ks; i++) {
            ll x = v2.v[i], t = 0;
            if (!x) continue;
            int j = i;
            for (; j >= 0; j--)
                if (x & (1 << j)) {
                    if (t1[j]) x ^= t1[j], t ^= t2[j];
                    else break;
                }
            if (!x) v[i] = t;
            else t1[j] = x, t2[j] = t;
        }
    }
 
    Type getmax()//获取最大值
    {
        Type ans = 0;
        for (int i = ks; i >= 0; i--) {
            ans = max(ans, ans ^ v[i]);
        }
        return ans;
    }
 
 
    ll Kth(ll k)//求第k大
    {
        if (!flag) {//如果没初始化过
            for (int i = 0; i <= ks; i++)
                p[i] = v[i];
            for (int i = 0; i <= ks; i++)
                for (int j = 0; j < i; j++)
                    if (p[i] & (1LL << j))
                        p[i] ^= p[j];
            for (int i = 0; i <= ks; i++) {
                if (p[i]) temp[num++] = p[i];
            }
            flag = 1;
        }
 
        if (n != num)//如果能构成异或为0
            k--;
        if (k >= (1LL << num)) {//如果超过 2^num-1个，则不能构成
            return -1;
        } else {
            ll ans = 0;
            for (int i = 0; i < num; i++) {//构成第k个数
                if (k & (1LL << i))
                    ans ^= temp[i];
            }
            return ans;
        }
    }
 
    bool check(ll x)//检查x是否能被线性基v表示
    {
        for (int i = ks; i >= 0; i--)
            if ((x >> i) & 1) x ^= v[i];
        return x == 0;
    }
} tr[4 * (50000) + 100];
 
void build(int o, int l, int r) { // 线段树自己写的时候还是出现了问题,所以这个是使用的网上的模板
    ll sz, x;
    if (l == r) {
        cin >> sz;
        for (int i = 0; i < sz; i++)
            cin >> x, tr[o].insert(x);
        return;
    }
    build(lc, l, mid);
    build(rc, mid + 1, r);
    tr[o].BaseInter(tr[lc], tr[rc]);
}
 
bool ask(int o, int l, int r, int s, int t, ll x) {
    if (s <= l && r <= t) return tr[o].check(x);
    int res = 1;
    // 分别判断左右区间,只有左右区间都可以才能认为此区间可以
    if (s <= mid) res &= ask(lc, l, mid, s, t, x);
    if (mid < t) res &= ask(rc, mid + 1, r, s, t, x);
    return res;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    build(1, 1, n);
    ll x;
    for (int l, r; m--;) {
        cin >> l >> r >> x;
        puts(ask(1, 1, n, l, r, x) ? "YES" : "NO");
    }
}

19杭电第一场1002

HDU6579

题意

给你一个序列,长度为n,然后给m个操作,操作有两种

第一种 询问l,r区间内的异或最大值

第二种 在末尾添加一个x

此题强制在线

解析

这个题当时杭电上通过的人还是很少的(一百个左右),但是看完题解之后觉得并不难实现,只是不好想.

我们发现这样一个问题:我们在之前维护线性基的时候,是几乎将其脱离了原数组,所以这个题我们一定要记录下线性基所对应的的原数组中的下标.

我们先回想线性基的几个性质:首先,线性基的插入顺序不会影响异或最大值的结果.而且对于第j位来说,我们只在乎当前插入的值的第j位是不是1,也就是如果有两个数他们第j位都是1,那么我们就不关心其插入顺序,甚至可以将他们互相置换.

换句话说,以下操作是合法的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void insert(Type x)//将x插入线性基v中
    {
        n++;
        for (int j = ks; j >= 0; j--) {
            if ((x >> j) & 1)
                if (!v[j]) {
                    v[j] = x;
                    break;
                } else {
                    swap(x, v[j]); // 让x替代原有的v[j]
                    x ^= v[j];
                }
        }
    }

其实经过更仔细的思考,我们发现可以这样,就是每次插入一个元素,就考虑这样更新一次线性基的所有元素,然后更新的原则是让它们在原数组中的下标尽可能的大 .为什么这样呢?其实线性基求异或最大值的原理就是按照每个二进制位去查看当前能不能取到1.

假设我们查找$[l,n]$,就是右端点一直是末尾的话,那么这个正确性是显然的. 因为根据暴力的做法,我们面对每个询问,都是要遍历线性基,如果在区间内,就考虑对其异或,然后输出答案.我们这个”置换”行为,不会缩小结果,反而会让元素的下标尽可能地在区间内,也就是尝试更优的答案.

但是题目的询问是$[l,r]$ ,并不一定在末尾截止.所以我们采取一种记忆化的方式,枚举所有元素作为区间的末尾,然后将其线性基保存下来(也就是在未插入后面的元素的时候的线性基先做个备份),然后询问的时候恢复现场(或者说从备份里直接查询也可以).

这种做法得益于线性基本身需要空间少,即使是面对接近1e6(原本5e5,但是可能插入5e5)的数据,也可以开的下.这个做法并不太适应于其他数据结构.

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

// 这个题有点卡空间,需要将线性基改成int
#include <bits/stdc++.h>
#define maxn 1000000+100
using namespace std;
int n, m;
const int ks = 31; // 切记,如果Type是ll,那么此处一定是63,是其他的可能会wa
typedef long long ll;
typedef int Type;
int pos[maxn];
int his_pos[maxn][ks + 1];
int his_val[maxn][ks + 1];

struct LinearBasis {
    Type v[ks + 1];//线性基
    int n = 0;
    LinearBasis() {
        memset(v, 0, sizeof(v));
    }

    void clear() {
        for (int j = ks; j >= 0; j--) {
            v[j] = 0;
        }
    }

    void insert(Type x, int pp)//将x插入线性基v中
    {
        n++;
        for (int j = ks; j >= 0; j--) {
            if ((x >> j) & 1)
                if (!v[j]) {
                    v[j] = x;
                    pos[j] = pp;
                    break;
                } else {
                    if (pp > pos[j]) {
                        swap(pp, pos[j]);
                        swap(x, v[j]);
                    }
                    x ^= v[j];
                }
        }
    }
};

LinearBasis a;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= 2 * n + 1; ++i) {
            pos[i] = 0;
            a.clear();
        }
        for (int i = 1; i <= n; ++i) {
            ll tmp;
            scanf("%lld", &tmp);
            a.insert(tmp, i);
            for (int j = ks; j >= 0; --j) { // 保存历史状态,下文的插入也是如法炮制
                his_pos[i][j] = pos[j];
                his_val[i][j] = a.v[j];
            }
        }
        int lastans = 0;
        for (int i = 0; i < m; ++i) {
            int op;
            scanf("%d", &op);
            if (!op) {
                ll l, r;
                scanf("%d%d", &l, &r);
                l = (l ^ lastans) % n + 1;
                r = (r ^ lastans) % n + 1;
                if (l > r)
                    swap(l, r);
                int ans = 0;
                for (int j = ks; j >= 0; j--) {
                    if (his_pos[r][j] >= l) {
                        ans = max(ans, ans ^ his_val[r][j]);
                    }
                }
                lastans = ans;
                printf("%d\n", ans);
            } else {
                int  x;
                scanf("%d", &x);
                x ^= lastans;
                ++n;
                a.insert(x, n);
                for (int j = ks; j >= 0; --j) {
                    his_pos[n][j] = pos[j];
                    his_val[n][j] = a.v[j];
                }
            }
        }
    }
    return 0;
}
CATALOG
    FEATURED TAGS
    CodeNote Web开发 软件工程 SpringBoot 互联网架构 垃圾回收的算法和实现 设计模式 android DAO 数据库 Python Vue Linux Unity VSCode学习 操作系统 版本控制 C++ View Java Kotlin Missing-Semester
    FRIENDS