【学习笔记】线性基

真正线性基的定义需要扯到线代那一部分。因为心情不好,所以鸽了。

此处主要讨论的线性基定义在异或运算上。即考虑给出一系列整数,称其中某个可以通过异或运算表出全部元素的子集为一组生成子集,称一组彼此都不能被表出元素为线性无关集。那么线性基就是一组线性无关生成子集

如果把每个数看成一个 $01$ 向量。可以如是做的原因是位运算时位位独立,就如同系数矩阵在做初等变换时行、列分别独立一样。所以这个线性空间内基的个数就是这个 $01$ 矩阵的秩。换句话说,求这个的过程完全可以通过高斯消元来实现。

基本操作

(1)插入

普通的插入顺便消了消元:

1
2
3
4
5
6
7
8
9
10
11
12
13
bool ins(LL y) {
bool ret = 0 ;
for (int i = M ; ~i ; -- i)
if (1ll << i & y) {
if (!x[i]) {
x[i] = y ;
ret = 1 ;
break ;
} else
y ^= x[i] ;
}
return ret;
}

大概消成的就是一个倒三角矩阵。显然最后 $x_i$ 有值的位数就是这个矩阵的秩。

虽然这样插入没错,但有一种更精妙的插入方式。这样插入之后可以保证线性基内至多存在 $1$ 个 $b_i$ 位为 $1$ 的数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool ins(LL y) {
bool ret = 0 ;
for (int i = M ; ~i ; -- i)
if (1ll << i & y) {
if (!x[i]) {
x[i] = y ; ret = 1 ;
for (int j = i - 1 ; j >= 0 ; -- j)
if (x[j] && (y >> j & 1)) x[i] ^= x[j] ;
for (int j = i + 1 ; j <= M ; ++ j)
if (x[j] >> i & 1) x[j] ^= x[i] ;
break ;
} else
y ^= x[i] ;
}
return ret;
}

这样消出来的就可以保证是一个部分对角的矩阵,比上三角矩阵有着更优秀的性质。

(2)询问

询问操作常(我)见(会)的,首先是求最大值/最小值,这东西显然贪心一遍即可:

1
2
for (int i = M ; ~i ; -- i)
ans = max/min(ans, ans ^ x[i]) ;

这种感觉。从大到小枚举不是因为贪心顺序,是因为这样可以保证消元消出来没有后效性。

然后是询问第 $k$ 小/大。这东西的话,考虑对于这个线性空间,一共可以张成 $2^n$ 个值。特判掉 $0$ 之后,发现对 $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
const int M = 63 ;
const int N = 100010 ;

bool haha ; LL z ;
int n, m, cnt ; LL ans ;
LL base[N], x[M + 1], rst[M + 1] ;

bool ins(LL y) {
bool ret = 0 ;
for (int i = M ; ~i ; -- i)
if (1ll << i & y) {
if (!x[i]) {
x[i] = y ; ret = 1 ;
for (int j = i - 1 ; j >= 0 ; -- j)
if (x[j] && (y >> j & 1)) x[i] ^= x[j] ;
for (int j = i + 1 ; j <= M ; ++ j)
if (x[j] >> i & 1) x[j] ^= x[i] ;
break ;
} else
y ^= x[i] ;
}
return ret;
}
LL query(LL k){
LL res = 0 ;
if (!haha) -- k ;
if (!k) return 0 ;
if (k >= (1ll << cnt)) return -1 ;
for (int i = 0 ; i < cnt ; ++ i)
if (k & (1ll << i)) res ^= rst[i] ;
return res ;
}
int main(){
cin >> n ; haha = 1 ;
for (int i = 1 ; i <= n ; ++ i)
cin >> base[i], haha &= ins(base[i]) ;
cin >> m ; //cout << haha << endl ;
cnt = 0 ;
for (int i = 0 ; i <= M ; ++ i)
if (x[i]) rst[cnt ++] = x[i] ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%lld", &z), printf("%lld\n", query(z)) ;
return 0 ;
}

题目是 loj#114 k大异或和

(3)删除

这部分我很迷啊…

首先如果可以离线就可以线段树分治,剩下的先鸽着。

大概就是考虑如果删除了一个不在线性基内的数,那就无所谓了。如果在其中,那么

经典应用

[WC2011]最大XOR和路径

考虑一个边权为非负整数的无向连通图,节点编号为 $1$ 到 $N$,试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得路径上经过的边的权值的 $\operatorname{XOR}$ 和最大。

$1\leq n,m\leq 10^6$

一道很经典的题。大概是维护异或生成树。

考虑这题先随便生成一条 $1\sim n$ 的路径,这样就是钦定了一颗生成树,那么剩下的会是一些圈。考虑从这条路径走出去,走完剩下的圈再走回来是一个来回,中间的桥边(装作)会被经过两次,所以不需要考虑。

所以 dfs 一遍就行。遇到环就丢到线性基里面,否则记录一下。

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
void Ins(LL x){
for (int i = B ; ~ i ; -- i)
if (1ll << i & x){
if (base[i]) x ^= base[i] ;
else return base[i] = x, void() ;
}
}
LL Query(LL basic){
LL ret = basic ;
for (int i = B ; ~i ; -- i)
ret = max(ret, ret ^ base[i]) ;
return ret ;
}
void add(int u, int v, LL w){
to(++ cnt) = v, val(cnt) = w ;
next(cnt) = head[u], head[u] = cnt ;
to(++ cnt) = u, val(cnt) = w ;
next(cnt) = head[v], head[v] = cnt ;
}
void dfs(int u, LL res){
f[u] = res, vis[u] = 1 ;
for (int k = head[u] ; k ; k = next(k))
if (!vis[to(k)])
dfs(to(k), res ^ val(k)) ;
else Ins(res ^ val(k) ^ f[to(k)]) ;
}
int main(){
cin >> n >> m ;
int u, v ; LL w ;
for (int i = 1 ; i <= m ; ++ i)
cin >> u >> v >> w, add(u, v, w) ;
dfs(1, 0) ; printf("%lld\n", Query(f[n])) ;
}