线性基学习笔记
发表更新ICPC/CCPC / Notes15 分钟读完 (大约2318个字)

线性基学习笔记

参考博客：1 2 3 4

基本思想

可以类比线性代数中的向量空间学习。

从二进制的角度看待每个数，每一位可以类比为向量空间的一维，每一维只有 $0$ 和 $1$ 两种取值。$n$ 个数就是 $n$ 个 $64$ 维的向量（long long 为例），它们构成了 $64$ 维向量空间的一个子空间。这个子空间中允许异或运算，两个向量相异或即每一维相异或。

线性基是一组数，构成这个子空间的一个基底，也即满足以下性质：

  • 原集合的任一元素可由线性基中的一些元素相异或得到；
  • 线性基是满足上述条件的最小集合；
  • 线性基没有异或为 $0$ 的子集：否则违背第二条；
  • 线性基的选取元素方案不同，异或值不同：否则存在子集异或为 $0$.

线性基的构造方式：

设 $p[]$ 是存储线性基中的数组，$p[i]$ 存储最高位为 $i$ 的数字。向线性基中插入一个数 $x$ 时，从高位向低位扫描，当扫到第 $k$ 位时，若 $p[k]$ 为 $0$，则 $p[k]$ 置为 $x$；否则 $x$ 异或上 $p[k]$. 代码如下：

1
2
3
4
5
6
7
inline void insert(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; break; }
        else    x ^= p[i];
    }
}

原因是：若 $p[k]=0$，则线性基中目前无法将 $x$ 异或出来，必须将 $p[k]$ 置为 $x$；否则，可以选出 $p[k]$ 将第 $k$ 位搞定，然后 $x$ 异或上 $p[k]$ 继续去匹配。

本质上其实和线性代数中初等行变换化上三角矩阵是一个道理，把 $p[]$ 数组一行一行写下来，大的在上，小的在下，就形成了一个上三角矩阵（不管不存在的维）。

有些题目可能还要化标准型矩阵，需要进行高斯消元：

1
2
3
4
5
6
7
inline void norm(){
    for(int i = 62; i >= 0; i--)
        if(p[i])
            for(int j = 62; j > i; j--)
                if((p[j] >> i) & 1)
                    p[j] ^= p[i];
}

模板

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

int n;
LL a;

LL p[70];
inline bool insert(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; return true; }
        else    x ^= p[i];
    }
    return false;
}
inline void norm(){
    for(int i = 62; i >= 0; i--)
        if(p[i])
            for(int j = 62; j > i; j--)
                if((p[j] >> i) & 1)
                    p[j] ^= p[i];
}
inline bool exist(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i])   return false;
        else    x ^= p[i];
    }
    return true;
}
inline LL xorMax(){
    LL res = 0;
    for(int i = 62; i >= 0; i--)
        res = max(res, res ^ p[i]);
    return res;
}
inline LL xorMin(){
    for(int i = 0; i <= 62; i++)
        if(p[i])    return p[i];
    return 0;
}
inline LL kthMin(LL k){ // kth minimum number (excluding 0)
    LL res = 0;
    vector<LL> tmp;
    for(int i = 0; i <= 62; i++)
        if(p[i])    tmp.push_back(p[i]);
    if(k >= (1ll << tmp.size()))    return -1;
    for(int i = tmp.size() - 1; i >= 0; i--)
        if((k >> i) & 1)    res ^= tmp[i];
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a);
        insert(a);
    }
    printf("%lld\n", xorMax());
    return 0;
}

练习

luoguP3812 【模板】线性基

题目链接

任取数使得异或值最大。

从大到小考虑线性基中的数，若异或上它之后答案变大则异或，否则不异或。

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

int n;
LL a;

LL p[70];
inline void insert(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; break; }
        else    x ^= p[i];
    }
}
inline LL xorMax(){
    LL res = 0;
    for(int i = 62; i >= 0; i--)
        res = max(res, res ^ p[i]);
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a);
        insert(a);
    }
    printf("%lld\n", xorMax());
    return 0;
}

hdu3949 XOR

题目链接

求第 $k$ 小异或值。

设线性基中基向量从大到小依次为 $\mathbf{v_0,v_1,\cdots,v_{m-1}}$（已经标准化了之后），则这个线性空间中第 $k=(b_x\cdots b_0)_2$ 小的数为

根据二进制不难证明。

>folded
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
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 10005;

int n, q;
LL p[70];
bool zero;

inline bool insert(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; return true; }
        else    x ^= p[i];
    }
    return false;
}
inline void norm(){
    for(int i = 62; i >= 0; i--)
        if(p[i])
            for(int j = 62; j > i; j--)
                if((p[j] >> i) & 1)
                    p[j] ^= p[i];
}
inline LL kthMin(LL k){ // kth minimum number (excluding 0)
    LL res = 0;
    vector<LL> tmp;
    for(int i = 0; i <= 62; i++)
        if(p[i])    tmp.push_back(p[i]);
    if(k >= (1ll << tmp.size()))    return -1;
    for(int i = tmp.size() - 1; i >= 0; i--)
        if((k >> i) & 1)    res ^= tmp[i];
    return res;
}

int main(){
    int T; scanf("%d", &T);
    for(int CASES = 1; CASES <= T; CASES++){
        printf("Case #%d:\n", CASES);
        scanf("%d", &n);
        memset(p, 0, sizeof p);
        zero = false;
        for(LL i = 1; i <= n; i++){
            LL a; scanf("%lld", &a);
            if(!insert(a))    zero = true;
        }
        norm();
        scanf("%d", &q);
        while(q--){
            LL k; scanf("%lld", &k);
            printf("%lld\n", kthMin(k - zero));
        }
    }
    return 0;
}

[BJWC2011]元素

题目链接

按法力从大到小排序，依次往线性基中插入元素时，若能插入则加上它的法力；否则扔掉。

贪心正确性：如果某个子集异或为 $0$，必然需要扔掉一个矿石，当然是扔掉法力最小的矿石啦。无法插入线性基的意义即它与之前的某些矿石形成的集合异或为 $0$，排序后它就是最小法力的矿石，不管它即可。

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 1005;

int n;

LL ans;
struct Node{
    LL num, magic;
    bool operator < (const Node &A) const{
        return magic > A.magic;
    }
}a[N];

LL p[70];
inline bool insert(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; break; }
        else    x ^= p[i];
    }
    return x != 0;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].num, &a[i].magic);
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; i++)
        if(insert(a[i].num))
            ans += a[i].magic;
    printf("%lld\n", ans);
    return 0;
}

[TJOI2008]彩灯

题目链接

输出子空间的大小，即 $2$ 的线性基大小次幂即可。

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 55;

int n, m, cnt;
char s[N];

LL p[70];
inline void insert(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; cnt++; break; }
        else    x ^= p[i];
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        scanf("%s", s);
        LL a = 0;
        for(int j = 0; j < n; j++)
            if(s[j] == 'O')
                a |= (1ll << j);
        insert(a);
    }
    printf("%lld\n", (1ll << cnt) % 2008);
    return 0;
}

[SCOI2016]幸运数字

题目链接

倍增lca + 线性基

>folded
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
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 20001;

inline void insert(LL p[], LL x){
    for(int i = 60; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; break; }
        else    x ^= p[i];
    }
}
inline void merge(LL p[], LL q[]){
    for(int i = 0; i <= 60; i++)
        if(q[i])
            insert(p, q[i]);
}
inline LL xorMax(LL p[]){
    LL res = 0;
    for(int i = 60; i >= 0; i--)
        res = max(res, res ^ p[i]);
    return res;
}

int n, q;
LL g[N], p[N][21][61];

struct Edge{
    int nxt, to;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to){
    edge[++edgeNum].nxt = head[from];
    edge[edgeNum].to = to;
    head[from] = edgeNum;
}

int fa[N][21], dep[N];
void dfs(int x, int f, int depth){
    dep[x] = depth;
    fa[x][0] = f;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f)	continue;
        dfs(edge[i].to, x, depth+1);
    }
}
void init(){
    for(int j = 1; (1 << j) <= n; j++)
        for(int i = 1; i <= n; i++)
            if(fa[i][j-1]){
                fa[i][j] = fa[fa[i][j-1]][j-1];
                merge(p[i][j], p[i][j-1]);
                merge(p[i][j], p[fa[i][j-1]][j-1]);
            }
}
inline LL lca(int x, int y){
    LL ans[61] = {0};
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 20; i >= 0; i--)
        if(dep[x] - (1 << i) >= dep[y])
            merge(ans, p[x][i]), x = fa[x][i];
    if(x == y)	return merge(ans, p[x][0]), xorMax(ans);
    for(int i = 20; i >= 0; i--){
        if(fa[x][i] && fa[x][i] != fa[y][i]){
            merge(ans, p[x][i]), merge(ans, p[y][i]);
            x = fa[x][i], y = fa[y][i];
        }
    }
    merge(ans, p[x][0]), merge(ans, p[y][0]);
    merge(ans, p[fa[x][0]][0]);
    return xorMax(ans);
}

int main(){
    read(n, q);
    for(int i = 1; i <= n; i++){
        read(g[i]);
        insert(p[i][0], g[i]);
    }
    for(int i = 1; i < n; i++){
        int u, v; read(u, v);
        addEdge(u, v), addEdge(v, u);
    }
    dfs(1, 0, 1);
    init();
    while(q--){
        int u, v; read(u, v);
        printf("%lld\n", lca(u, v));
    }
    return 0;
}

[WC2011]最大XOR和路径

题目链接

从一个点出发，到某个圈绕一圈之后再原路返回，就白嫖到了这个圈的异或和。所以把所有圈的异或和丢进线性基，再任意找一条从 $1$ 到 $n$ 的路径在线性基中询问即可。（任意找的原理是：即使当前路径不是最优的，最优路径一定会与它形成了若干圈，异或这些圈就能自动修正成最优路径）

>folded
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
#include<algorithm>
#include<cstdio>
#include<cmath>

using namespace std;

typedef long long LL;

const int N = 50005;
const int M = 100005;

int n, m;

LL p[70];
inline void insert(LL x){
    for(int i = 62; i >= 0; i--){
        if((x >> i) == 0)   continue;
        if(!p[i]){ p[i] = x; break; }
        else    x ^= p[i];
    }
}

struct Edge{
    int nxt, to;
    LL dis;
}edge[M<<1];
int head[N], edgeNum;
void addEdge(int from, int to, LL dis){
    edge[++edgeNum] = (Edge){head[from], to, dis};
    head[from] = edgeNum;
}

LL dis[N];
bool vis[N];
void dfs(int x, int f){
    vis[x] = 1;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f) continue;
        if(vis[edge[i].to]) insert(dis[edge[i].to] ^ dis[x] ^ edge[i].dis);
        else    dis[edge[i].to] = dis[x] ^ edge[i].dis, dfs(edge[i].to, x);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        int u, v; LL d;
        scanf("%d%d%lld", &u, &v, &d);
        addEdge(u, v, d), addEdge(v, u, d);
    }
    dfs(1, 0);
    LL ans = dis[n];
    for(int i = 62; i >= 0; i--)
        ans = max(ans, ans ^ p[i]);
    printf("%lld\n", ans);
    return 0;
}

线性基学习笔记

http://xyfjason.github.io/blog-xcpc/2020/03/10/线性基学习笔记/

作者

xyfJASON

发布于

2020-03-10

更新于

2021-02-25

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×