MinamiMelon
0%

线性基学习记录

发表于 更新于

向量空间:给定域\(F\)，\(F\)上的向量空间\(V\)是一个集合，其上定义加法和数乘运算且这两个运算满足八个公理。

线性无关:对于向量空间中\(V\)上\(n\)个元素的向量组\((\mathbf{v}_1, \ldots, \mathbf{v}_n)\),若存在不全为\(0\)的数\(a_i \in F\)满足 \[ a_{1}\mathbf{v}_{1}+a_{2}\mathbf {v}_{2}+\ldots +a_{n}\mathbf{v}_{n} = 0 \]

则称这\(n\)个向量线性相关（linearly dependent），否则称为线性无关（linearly independent）。

线性组合:对于向量空间中 V 上 nn 个元素的向量组\((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其线性组合（linear combination）是如下形式的向量

\[ a_{1}\mathbf{v}_{1} + a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n} \] ​​ 其中\(a_1, \ldots, a_n \in F\)

一组向量线性无关 \(\Leftrightarrow\)没有向量可用有限个其他向量的线性组合所表示

张成:对于向量空间中 \(V\) 上 \(n\) 个元素的向量组 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其所有线性组合所构成的集合称为 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)的张成（span），记为 \(\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)\)

基:若向量空间 \(V\) 中向量组 \(\mathfrak{B}\) 既是线性无关的又可以张成 \(V\)，则称其为\(V\) 的基（basis）。

\(\mathfrak{B}\)中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

设 \(\mathfrak {B}\) 是向量空间 \(V\) 的基。则\(\mathfrak {B}\)具有以下性质：

1.\(V\) 是 \(\mathfrak {B}\)的极小生成集，就是说只有\(\mathfrak {B}\)能张成\(V\)，而它的任何真子集都不张成全部的向量空间。

2.\(\mathfrak {B}\) 是 \(V\) 中线性无关向量的极大集合，就是说 \(\mathfrak {B}\) 在\(V\) 中是线性无关集合，而且\(V\) 中没有其他线性无关集合包含它作为真子集。

3.\(V\) 中所有的向量都可以按唯一的方式表达为\(\mathfrak {B}\) 中向量的线性组合。

异或运算下的基} $

对于数 \(a_0, a_1, \ldots, a_n\)，将 \(a_i\)的二进制表示$ (b_{m}b_0)_2$​ 看作一个向量。向量组 \(\mathbf{a}_1, \ldots, \mathbf{a}_n\)可以张成一个向量集合 \(\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n)\)，加上我们的异或运算和乘法运算（显然满足 8 条公理），即可形成一个向量空间 \(V = (\{0, 1\}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)\)

设集合\(S\)中最大的数在二进制意义下有\(L\)位，我们使用一个 \([0\dots L]\)的数组\(a\)来储存线性基。

这种线性基的构造方法保证了一个特殊性质，对于每一个\(i\),\(a_i\)有以下两种可能：

  • \(a_i=0\)，并且 只有} \(满足\)j<i\(的\)a_j\(（即\)a_i\(前面所有数）的第\)i$个二进制位一定为\(0\)。

  • \(a_i\neq0\),并且

  1. 整个\(a\)数组只有\(a_i\)的第\(i\)个二进制位为\(1\)；
  2. \(a_i\)更高的二进制位一定为1

（如果排成矩阵，形成一个下三角矩阵）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
const int MAXL=60;
ll a[MAXL+1];int lbsiz;
void insert(ll t){//高斯消元解出的对角矩阵的非零行构成的向量组 
    for(int j=MAXL;j>=0;--j){// 逆序枚举二进制位
        if(!((t>>j)&1)) continue;// 如果 t 的第 j 位为 0，则跳过
        if(a[j]) t^=a[j];
        else{// 找到可以插入 a[j] 的位置
            // 用 a[0...j - 1] 消去 t 的第 [0, j) 位上的 1
// 如果某一个a[k]=0也无须担心，因为这时候第k位不存在于线性基中，不需要保证t的第k位为 0	
            for(int k=0;k<j;++k) if((t>>k)&1) t^=a[k];
            // 用 t 消去 a[j + 1...L] 的第 j 位上的 1
            for(int k=j+1;k<=MAXL;++k) if((a[k]>>j)&1) a[k]^=t;
                // 插入到 a[j] 的位置上
            a[j]=t;++lbsiz;
            return;// 不要忘记，结束插入过程
        }
    }
}

最大异或和：将线性基中所有向量异或起来得到的向量所对应的数。

1
2
3
4
5
ll querymax(){
    ll res=0;
    for(int i=0;i<=MAXL;++i) res^=a[i];
    return res;
}

集合任选大于1个元素异或出的第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
vector<ll> v;
bool zero;int n;//zero: 是否能异或出0
void init(){
    lbsiz=0;
    v.clear();
    memset(a,0,sizeof a);
}
void prepare(){
    zero=(lbsiz!=n);
    for(int i=0;i<=MAXL;++i){
        if(a[i]) v.push_back(a[i]);
    }
}
ll query(ll k){
    if(zero) --k;
    if(k>=(1ll<<v.size())) return -1;
    ll res=0;
    for(int i=MAXL;i>=0;--i) if((k>>i)&1) res^=v[i];
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int ttt=1;ttt<=T;++ttt){
        init();
        scanf("%d",&n);ll t;
        for(int i=1;i<=n;++i){
            scanf("%lld",&t);
            insert(t);
        }
        prepare();
        printf("Case #%d:\n",ttt);
        int q;scanf("%d",&q);
        while(q--){
            scanf("%lld",&t);
            printf("%lld\n",query(t));
        }
    }
    return 0;
}

P4151 [WC2011]最大XOR和路径

异或路径问题：转化成任意一条路径，和任意个圈的异或。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int M=200000+5,N=50000+5,MAXL=60;
struct Edge{
	int t,n;
	ll v;
}e[M];
int hd[N],cnt;
inline void build(int f,int t,ll v){
	e[++cnt]=(Edge){t,hd[f],v};
	hd[f]=cnt;
}
ll a[MAXL+3],dis[N];
bool vis[N];
void insert(ll t){
	for(int j=MAXL;j>=0;--j){
		if(!((t>>j)&1)) continue;
		if(a[j]) t^=a[j];
		else{
			for(int k=0;k<j;++k){
				if((t>>k)&1) t^=a[k];
			}
			for(int k=j+1;k<=MAXL;++k){
				if((a[k]>>j)&1){
					a[k]^=t;
				}
			}
			a[j]=t;
			return;
		}
	}
}
int n,m;
void dfs(int u,ll now){
	dis[u]=now;vis[u]=1;
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(!vis[v]){
			dfs(v,now^e[i].v);
		}else{
			insert(now^e[i].v^dis[v]);
		}
	}
}
ll query(ll x){
	for(int i=MAXL;i>=0;--i){
		if((x^a[i])>x){
			x^=a[i];
		}
	}
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b;ll d;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&a,&b,&d);
		build(a,b,d);
		build(b,a,d);
	}
	dfs(1,0);
	printf("%lld",query(dis[n]));
	return 0;
}

P4301 [CQOI2013] 新Nim游戏

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
#include<bits/stdc++.h>
using namespace std;

const int N=105;
int a[40],d[N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
	}
	sort(d+1,d+n+1,greater<int>());
	long long ans=0;
	for(int i=1;i<=n;++i){
		int t=d[i];
		for(int j=31;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				a[j]=t;
				break;
			}
		}
		if(!t) ans+=d[i];
	}
	printf("%lld",ans);
	return 0;
}

P3292 [SCOI2016]幸运数字

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=20000+5,MAXL=61;
struct Edge{
	int t,n;
}e[N<<1];
int hd[N],cnt;
inline void build(int f,int t){
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
}
struct Lbasis{//Linear Basis 
	ll a[MAXL+1];
	Lbasis(){memset(a,0,sizeof a);}
	Lbasis(const Lbasis& b){memcpy(a,b.a,sizeof a);} 
	void insert(ll t){
		for(int j=MAXL;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				for(int k=0;k<j;++k){
					if((t>>k)&1) t^=a[k];
				}
				for(int k=j+1;k<=MAXL;++k){
					if((a[k]>>j)&1){
						a[k]^=t;
					}
				}
				a[j]=t;
				return;
			}
		}
	}
	void merge(const Lbasis &b){
		for(int i=MAXL;i>=0;--i){
			if(b.a[i]){
				insert(b.a[i]);
			}
		}
	}
	ll max(){
		ll res=0;
		for(int i=0;i<=MAXL;++i){
			res^=a[i];
		}
		return res;
	}
}b[20][N];
int dep[N],anc[20][N];
ll val[N];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	anc[0][u]=f;
	b[0][u].insert(val[u]);
	for(int i=1;anc[i-1][u];++i){
		anc[i][u]=anc[i-1][anc[i-1][u]];
		b[i][u]=b[i-1][u];
		b[i][u].merge(b[i-1][anc[i-1][u]]);
	}
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(v==f) continue;
		dfs(v,u);
	}
}
ll ask(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int dd=dep[x]-dep[y];
	Lbasis res;
	for(int i=19;i>=0;--i){
		if(dd&(1<<i)){
			res.merge(b[i][x]);
			x=anc[i][x];
		}
	}
	if(x==y){
		res.insert(val[x]);
		return res.max();
	}
	for(int i=19;i>=0;--i){
		if(anc[i][x]!=anc[i][y]){
			res.merge(b[i][x]);res.merge(b[i][y]);
			x=anc[i][x];y=anc[i][y];
		}
	}
	res.insert(val[x]);res.insert(val[y]);res.insert(val[anc[0][x]]);
	return res.max();
}
int n;
int main(){
	int q;
	scanf("%d%d",&n,&q);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%lld",&val[i]);
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		build(a,b);build(b,a);
	}
	dfs(1,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%lld\n",ask(x,y));
	}
	return 0;
}