1. 前置知识

1. 线性有关/无关：
   知乎中有对线性相关与线性无关比较具象化的解释。可以发现，线性基就是一种线性无关构成的线性相关的集合。
2. 张成：
   就是线性基的组成的集合。
3. 基
   三个性质都很好理解，注意\(span(B)\)表示一个张成空间（属于集合）。
4. 线性相关引理
   就是线性相关性质，没啥好说的。

2.OI中的线性基

在OI中，“线性基”专用于解决有关异或的一些问题。

张成空间判定问题Ⅰ&Ⅱ

\(\centerdot\) 判定问题Ⅰ很好理解，参见P4151 [WC2011] 最大XOR和路径就是引理的基本运用。
\(\centerdot\) 判定问题Ⅱ利用了三角矩阵优化，思维很好。

实数域线性基

其实很常规，但是没想到。
如果像异或那样写出一个式子，那么他长得看起来很像高斯消元。
但是只用得到消元的全式子同除以一个系数的部分。
P3265 [JLOI2015] 装备购买

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;

inline int read(){
	int x = 0 ,y = 1 ;
	char c = getchar() ;
	while(c < '0' || c > '9'){
		if(c == '-')	y = -1 ;
		c = getchar() ;
	}
	while(c <= '9' && c >= '0'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * y ;
}

const int MAXN = 505 ;
const double eps = 1e-5 ;
int n ,m ;
struct Stuff{
	double z[MAXN] ;
	int cost ;
}s[MAXN] ;

inline bool cmp(Stuff a , Stuff b){
	return a.cost < b.cost ;
}

int tot ,ans ;
int lb[MAXN] ;
inline void add(int x){
	for(int i = 1;i <= m;++i){//枚举每一位 
		if(s[x].z[i] <= eps && s[x].z[i] >= -eps) continue ; 
		if(lb[i] == 0){
			lb[i] = x ;
			tot++ ;
			ans += s[x].cost ;
			return ;
		}else{
			double k = s[x].z[i] / s[lb[i]].z[i] ;//做差消掉这件商品的每一个已知lb 
			for(int j = i;j <= m;++j){
				s[x].z[j] -= k * s[lb[i]].z[j] ;
			}
		}
	}
}

int main(){
	n = read() ,m = read() ;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= m;++j)	scanf("%lf" , &s[i].z[j]) ;
	}
	for(int i = 1;i <= n;++i)	s[i].cost = read() ;
	sort(s+1 , s+1+n , cmp) ;
	for(int i = 1;i <= n;++i){//遍历到第i件物品 
		add(i) ;
	}
	printf("%d %d" , tot , ans) ;
	return 0 ;
} 

k小子集异或和

woc 5min一发过P3857 [TJOI2008] 彩灯
结论很好感性理解 感觉很好记
小心-1的情况

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std ;

const int MAXN = 55 ;

int n ,m ;
bitset<MAXN> num ;
bitset<MAXN> s[MAXN] ;
int tot ;
inline void add(bitset<MAXN> x){
	for(int i = 50;i >= 0;--i){
		if(x[i]){
			if(s[i].none() == false){
				x ^= s[i] ;
			}else{
				s[i] = x ;
				tot++ ;
				return ;
			}
		}
	}
}

int main(){
	scanf("%d%d" , &n , &m) ;
	for(int i = 1;i <= m;++i){
		char str[MAXN] ;
		scanf("%s" , str) ;
		for(int j = 0;j < n;++j){
			if(str[j] == 'O'){
				num[j] = 1 ;
			}else{
				num[j] = 0 ;
			}
		}
		add(num) ;
	}
	printf("%d" , (1ll << tot) % 2008) ;
	return 0 ; 
}

线性基合并

暴力合并即可。
P3292 [SCOI2016] 幸运数字

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std ;

const int MAXM = 2e4+10 ;

int n ,m ;
int jump[MAXM][17] ,dep[MAXM] ;
ll f[MAXM][17][62] ,lb[62] ;
ll val[MAXM] ;

struct Edge{
    int to ,next ;
}edge[MAXM<<1] ;
int head[MAXM] ,edge_cnt ;
inline void edge_add(int from , int to){
	edge[++edge_cnt].to = to ;
	edge[edge_cnt].next = head[from] ;
	head[from] = edge_cnt ;
}

inline void insert(ll *a , ll x){
    for(int i=60;i>=0;i--){
        if(!((x >> i) & 1ll)) continue ;
        if(!a[i]){
			a[i] = x ;
			return ;
		}
        else x ^= a[i] ;
    }
}

inline void merge(ll *a,ll *b){
    for(int i = 60;i >= 0;--i)	if(b[i]) insert(a , b[i]) ;
}

inline void dfs(int node , int fa){
    jump[node][0] = fa ;
    dep[node] = dep[fa] + 1 ;
    for(int i = 1;i <= 16;++i)
        if(jump[node][i-1]){
        	jump[node][i] = jump[jump[node][i-1]][i-1];
        	memcpy(f[node][i] , f[node][i-1] , sizeof f[node][i-1]) ; 
        	merge(f[node][i] , f[jump[node][i-1]][i-1]) ;
        }
    for(int i = head[node];i;i = edge[i].next){
    	int v = edge[i].to ;
        if(v == fa)	continue ;
        dfs(v , node) ;
    }
}

inline int LCA(int x , int y){
    if(dep[x]<dep[y]) swap(x , y) ;
    int dist = dep[x] - dep[y] ;
    for(int i = 16;i >= 0;--i){
        if((dist>>i) & 1)	merge(lb , f[x][i]) ,x = jump[x][i] ;
    }
    if(x == y) return x ;
    for(int i = 16;i >= 0;--i){
        if(jump[x][i] != jump[y][i]){
            merge(lb , f[x][i]) ;
			merge(lb , f[y][i]) ;
            x = jump[x][i] ;
			y = jump[y][i] ;
        }
    }
    merge(lb , f[x][0]) ;
    insert(lb , val[y]) ;
    return jump[x][0] ;
}

int main(){
    scanf("%d%d" , &n , &m) ;
    for(int i=1;i<=n;i++){
        ll a ;scanf("%lld" , &a) ;
        val[i] = a ;
        insert(f[i][0] , a) ;
    }
    for(int i = 1;i < n;++i){
    	int u ,v ;
        scanf("%d%d" , &u , &v) ;
        edge_add(u , v) ;
        edge_add(v , u) ;
    }
    dfs(1 , 0) ;
    while(m--){
        memset(lb , 0 , sizeof lb) ;
        int u , v ;scanf("%d%d" , &u , &v) ;
        int lca = LCA(u , v) ;
        merge(lb , f[lca][0]) ;
        ll ans = 0 ;
        for(int i = 60;i >= 0;--i)	ans = max(ans , ans ^ lb[i]) ;
        printf("%lld\n" , ans) ;
    }
    return 0 ;
}

P4839 P 哥的桶
线段树维护线性基合并时 三种合并query情况分开！不同区间的线性基不能合并！

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std ;

const int MAXN = 5e4+10 ;

int n ,m ;

struct Lb{
	int a[32] ;
	
	void insert(int x){
		for(int i = 31;i >= 0;--i)
			if(x & (1 << i)){
				if(a[i])	x ^= a[i] ;
				else{
					a[i] = x ;
					return ;
				}
			}
	}
	
	void merge(Lb n){
		for(int i = 31;i >= 0;--i)
			if(n.a[i])	insert(n.a[i]) ;
	}
}tree[MAXN<<2] ;

inline void update(int node , int li , int ri , int x , int delta){
	if(x < li || x > ri)	return ;
	tree[node].insert(delta) ;
	if(li == ri)	return ;
	int mid = (li + ri) >> 1 ;
	if(x <= mid)	update(node<<1 , li , mid , x , delta) ;
	else update(node<<1|1 , mid+1 , ri , x , delta) ;
}

Lb ans ;
inline void query(int node , int li , int ri , int l , int r){
	if(l <= li && ri <= r){
		ans.merge(tree[node]) ;
		return ;
	}
	int mid = li + ri >> 1 ;
	/*if(l <= mid)	query(node<<1 , li , mid , l , r) ;
	if(mid < r)	query(node<<1 , mid+1 , ri , l , r) ;*/
	if(r <= mid)	query(node<<1 , li , mid , l , r) ;//三种可能分清楚！ 
	else if(mid < l)	query(node<<1|1 , mid+1 , ri , l , r) ;
	else query(node<<1 , li , mid , l , mid) ,query(node<<1|1 , mid+1 , ri , mid+1 , r) ;
	//l r区间要分开！两边的线性基不能合并！ 
}

int maxx = 0 ;
int main(){
	scanf("%d%d" , &n , &m) ;
	for(int i = 1;i <= n;++i){
		int opt ;scanf("%d" , &opt) ;
		if(opt == 1){
			int k ,x ;scanf("%d%d" , &k , &x) ;
			update(1 , 1 , m , k , x) ;
		}else{
			int l ,r ;scanf("%d%d" , &l , &r) ;
			memset(ans.a,0,sizeof(ans.a));
			maxx = 0 ;
			query(1 , 1 , m , l , r) ;
			for(int j = 31;j >= 0;--j)	maxx = max(maxx , maxx ^ ans.a[j]) ;
			printf("%d\n" , maxx) ;
		}
	}
	return 0 ;
}

P4869 albus就是要第一个出场
推式子很好推 但是实现有较多细节。

#include<iostream>
#include<cstdio>
using namespace std ;

const int MAXN = 1e5+10 ;
const int mod = 10086 ;
int lb[MAXN] ;
int n ,id ;
int cnt = 1 ;

inline void insent(int x){
	for(int i = 30;i >= 0;--i){
		if((1 << i) & x){
			if(lb[i] == 0){
				lb[i] = x ;
				return ;
			}else{
				x ^= lb[i] ;
			}
		}
	}
	if(x == 0){//这个数可以被线性基表示 
		cnt = (cnt << 1) % mod ;//方案数*2 表示乘法原理多一位 
	}
}

int main(){
	scanf("%d" , &n) ;
	for(int i = 1;i <= n;++i){
		int x ;scanf("%d" , &x) ;
		insent(x) ;
	}
	scanf("%d" , &id) ;
	int rk = 0 ,tp = 1 ;
	for(int i = 0;i <= 30;++i){
		if(lb[i]){//线性基中有这位 说明可以计算 
			if((id >> i) & 1) rk += tp ;//需要利用线性基中的这位元素 加上2^i种情况 
			tp <<= 1 ;
		}
	}
	rk %= mod ;//大小上排这么多位 
	printf("%d" , ((rk * cnt == mod) ? 0 : ((rk * cnt + 1) % mod))) ;//每一个数都有一位乘法原理系数 
	return 0 ;
}

P5607 [Ynoi2013] 无力回天 NOI2017
有点麻烦。线段树套线性基，需要用树状数组维护差分。我猜这个做法是唯一维护线段树套线性基的方法。

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 5e4+10 ;

inline int read(){
	int x = 0 ,y = 1 ;
	char c = getchar() ;
	while(c < '0' || c > '9'){
		if(c == '-')	y = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * y ;
}

int n ,m ,w[MAXN] ,c[MAXN] ;
struct LB{
	int lb[35] ;
	inline void insert(int x){
		for(int i = 30;i >= 0;--i){
			if(x & (1 << i)) {
				if(lb[i]){
					x ^= lb[i] ;
				}else{
					lb[i] = x ;
					return ;
				}
			}
		}
	}
} ;

inline LB merge(LB x, LB y) {
	for(int i = 30;i >= 0;--i){
		if (y.lb[i]) x.insert(y.lb[i]) ;
	}
	return x ;
}

struct Segtree{
	LB tree[MAXN<<2] ;

	inline void build(int node , int l , int r){
		for(int i = l;i <= r;++i) tree[node].insert(w[i]) ;
		if(l == r) return ;
		int mid = l + r >> 1 ;
		build(node << 1, l, mid) ;
		build(node << 1 | 1, mid + 1, r) ;
		tree[node] = merge(tree[node << 1] , tree[node << 1 | 1]) ;
	}
	
	inline void update(int node , int li , int ri , int idx , int v){
		if(li == ri){
			memset(tree[node].lb, 0, sizeof tree[node].lb) ;
			tree[node].insert(w[li] ^= v) ;
			return ;
		}
		int mid = li + ri >> 1 ;
		if(idx <= mid) update(node << 1 , li , mid , idx , v) ;
		else update(node << 1 | 1 , mid + 1 , ri , idx , v) ;
		tree[node] = merge(tree[node << 1], tree[node << 1 | 1]) ;
	}
	
	inline LB query(int node , int li , int ri , int l , int r){
		if (li == l && ri == r) return tree[node] ;
		int mid = li + ri >> 1 ;
		if (mid >= r) return query(node << 1, li , mid , l , r) ;
		else if (mid + 1 <= l) return query(node << 1 | 1 , mid + 1 , ri , l , r) ;
		else return merge(query(node << 1 , li , mid , l , mid) , query(node << 1 | 1 , mid + 1 , ri , mid + 1 , r)) ;
	}
}seg ;

inline int lowbit(int x){
	return x & -x ;
}

inline void modify(int i , int x){
	for(int j = i;j <= n;j += lowbit(j)) c[j] ^= x ;
}

inline int trebitquery(int i){
	int ans = 0;
	for(int j = i;j >= 1;j -= lowbit(j)) ans ^= c[j] ;
	return ans ;
}

int main() {
	n = read(); m = read();
	for(int i = 1;i <= n;++i) w[i] = read() ;
	for(int i = n;i >= 2;--i) w[i] ^= w[i - 1] ;
	for(int i = 1;i <= n;++i) modify(i , w[i]) ;
	seg.build(1 , 1 , n) ;
	for(int i = 1;i <= m;++i){
		int opt = read(), l = read() ,r = read() ,v = read() ;
		if(opt == 1){
			modify(l , v) ;
			seg.update(1 , 1 , n , l , v) ;
			if(r < n) {
				modify(r + 1 , v);
				seg.update(1 , 1 , n , r+1 , v) ;
			}
		}else{
			int k = trebitquery(l) ;
			if(l == r){
				printf("%d\n" , max(k ^ v , v)) ;
			}else{
				LB ans = seg.query(1 , 1 , n , l+1 , r) ;
				ans.insert(k) ;
				for(int i = 29;i >= 0;--i){
					if ((v ^ ans.lb[i]) > v) v = (v ^ ans.lb[i]) ;
				}
				printf("%d\n" , v) ;
			}
		}
	}
	return 0 ;
}

带删除线性基

\(\centerdot\)强制在线
感觉就是纯分讨。没啥好说的。不会自己看blog。
\(\centerdot\)离线
就是P3733。
好像有不带log的解法。咕咕咕。

总结

感觉比较板。。。
实数域线性基没太想到。
关于数据结构部分还需练习。

本栏目推荐文章
• 【解决方案】Error running,Command line is too long
• 线性表
• devmapper: Thin Pool has 162394 free data blocks which is less than minimum required 163840 free data blocks
• 【机器学习】多元线性回归
• 【算法】【线性表】【链表】删除排序链表中的重复元素 II
• 【算法】【线性表】【链表】删除排序链表中的重复元素
• 用C#使用NumSharp实现简单的线性回归
• 用C#实现简单的线性回归
• 斜率优化小记
• 解决前后端的跨域问题：Access to XMLHttpRequest at '**' from origin '**' has been blocked by CORS policy: No 'Access-Control-Allow-Origin' header is present on the requested resource.

小记 线性 command_block command block小记 线性command_block command command_block command_block杂谈command block 线性代数 代数 小记 线性 对偶 小记 线性128036 小记 线性 block blocked blocking blocks