异或和与线性基问题入门

概述

在OI/ACM中，线性基一般特指布尔域上的基。由于布尔域和二进制关系密切，同时有限域只有有限状态，所以容易被出成题。

线性基用于解决子集异或和有关的问题。例如要求查询“任选几个数，使其异或和最大”。如果题目要求并非“任选”而是有所限制，一般无法用线性基解决，因为求基后无法满足限制条件。

基本操作

线性基的性质

求“任选几个数异或和的所有可能值”，实际上就是把这些数视为二进制向量，求它们张成的线性空间。
根据线性代数知识，可以对这些向量进行初等行变换，而不影响结果。因此我们把它化为行阶梯型矩阵，或行最简形矩阵。
这样，就消除了多余的变量，得到一组基向量。如果化为行最简型，那么这样的基是唯一的。

观察这个阶梯型或最简型，只有每行行首所在的列01可以任意变动。所有可能异或和的个数，自然就是 \(2^{\mathbb{dim}\ \mathbb{linspan}(vec)} \)，即2的矩阵秩次幂。
所以任意输入一个数(二进制向量)，只需要用这些关键列确定它应该是由哪几个基组成，以及判断它是否合法。

这样行阶梯型求出来的基具有很好的性质，可直接从高位到低位贪心得到最大值，实际上也是线性拟阵的一个例子。
如果要求最小值，则显然是最小的那个基向量。

线性基常见模板

如下代码就表示了维护行阶梯型，并求最大值的代码。我们仍使用数字表示一个布尔向量，于是unsigned long long范围内，最多有64个基。
用base[i]表示首位位置在i上的基向量，否则为0。则base本身是个上三角矩阵，base中的非零值就形成一个阶梯型矩阵，这种表示相当方便。
有时最简形更实用，比如用于求解kth。可以直接在加入过程中维护最简形，需要先把base[i]本身可以清零的位异或掉，再把大于base[i]的基第i列异或掉。也可以再需要时再把阶梯型化为最简形。
求kth时，只需把关键列调整位二进制的k即可。

```
//we may need <bitset> sometimes
```
```
typedef unsigned long long ll;
```
```
ll base[64];
```
```
void add(ll x){
```
```
	for (int i=63;i>=0;i--)
```
```
		if (x&1ull<<i)
```
```
			if (!base[i]){
```
```
				base[i]=x;
```
```
				return;
```
```
			}
```
```
			else x^=base[i];
```
```
}
```
```
 
```
```
//test if x can perform by xor sum
```
```
bool test(ll x){
```
```
	for (int i=63;i>=0;i--)
```
```
		if (x&1ull<<i)
```
```
			if (!base[i]) return 0;
```
```
			else x^=base[i];
```
```
	return 1;
```
```
}
```
```
 
```
```
//max xor sum
```
```
ll maxc(){
```
```
	ll ans=0;
```
```
	for (int i=63;i>=0;i--)
```
```
		if ((ans^base[j])>ans)
```
```
			ans^=base[i];
```
```
	return ans;
```
```
}
```
```
 
```
```
//min xor sum
```

ll minc(){for (int i=0;i<64;i++) if (base[i]) return base[i];}

```
 
```
```
//query kth max number
```

//k should not larger than 2^(dim linspan(x))

```
ll kth(ll k){
```
```
	ll ans=0,tmp[64],res=0,cnt=0;
```

    for(T i=0;i<64;i++){ //set matrix to simplest form

```
        for(int j=i-1;j>=0;j--)
```

			if(base[i]&1ull<<j) base[i]^=base[j];

```
        if(base[i])tmp[cnt++]=base[i];
```
```
    }
```
```
//!!error here
```
```
	for (int i=63;i>=0;i--)
```
```
		if (k&1ull<<i)
```
```
			ans^=base[i];
```
```
	return ans;
```
```
}
```

加强版

加长

如果布尔向量很长，上述代码可改用bitset。但要注意，和高斯消元一样，时间复杂度达到O(n^3)，空间复杂度O(n^2)，只是常数很小。

线性基合并，区间和问题

两个线性空间W1,W2，它们的集合并W1∪W2不一定是个线性空间，也就不存在线性基。我们这里说的线性基合并，是指线性空间的和：{W1+W2}。

合并两个线性基只能一个个插入O(n^3)，没有复杂度更优的做法。然而平时的一些题目中，数据范围不会很大，例如32位整数或64位整数。这时即使数据量很大，写出来是个又瘦又高的矩阵，它的线性基也只能是那么多个。

如果我们把单次合并视为常数时间，那大概是32*32这样的大常数。

有了这个思想，看看这个问题：(2017西安区域赛A)询问区间内某个子集异或和再异或上k的最大可能值。
前面说过，线性基无法回答某个子集异或和这种非整体性的问题，所以这道题中，我们求出的是所有询问区间的线性基。既然线性空间的并运算是可交换可结合的，那么暴力预处理出线段树，在线段树上合并区间即可。
时间复杂度：O(nlog(n)*d^2)+O(Qlog(n)*d^2)，d为数据位数。
空间复杂度：O(n*d)

线性空间交

两个线性空间交必然是线性子空间。想要求出交空间的线性基，有以下结论：

设{α}是V1的基，{β}是V2的基，W={β}∩V1。若 {α}∪({β}-W) 线性无关，则W是交空间的基。

我们想要求出W，方法是先尝试合并为线性基tmp，即在{α}的基础上依此插入{β}的元素。同时，记录线性基tmp中由{α}贡献的部分。若尝试插入βi的是两个空间的交叠部分，必然与tmp产生线性相关无法插入。注意到此时βi是由V1和V2合并得到的基向量线性表出；而根据定义，βi可以只用{α}线性表出，所以把它由tmp中{α}贡献的部分加入答案。(把{β}贡献的部分加入答案也可)

```
Basis Ingersect(Basis &A, Basis &B){
```
```
    Basis tmp=A,v1=A,v2=B, ans;
```
```
    for(LL i=0;i<32;i++){
```
```
        if(v2.basis[i]){
```
```
            bool flag=true;
```
```
            LL x=v2.basis[i],now=0;
```
```
            for(LL j=31;j>=0;j--)
```
```
                if(x&(1ll<<j)){
```
```
                    if(!tmp.basis[j]){
```

                        flag=false; //can't be represent

                        tmp.basis[j]=x; //so insert

                        v1.basis[j]=now;

```
                        break;
```
```
                    }
```

                    x^=tmp.basis[j]; //same as Basis.insert

```
                    now^=v1.basis[j];
```
```
                }
```
```
            if(flag) ans.insert(now);
```
```
        }
```
```
    }
```
```
    return ans;
```
```
}
```

构建全部子空间

虽然所有相同维数的线性子空间是同构的，具有完全相同的代数性质；或者说，忽视列之间的区别进行初等列变换，得到等价标准型是相同的。但有时，题目中仍要求区分不同的列，所以不能进行列变换。

既然一个矩阵化为行最简形矩是唯一的，那么一个行最简形确定了一个线性子空间。
我们不妨猜测一下这样的子空间有多少个，例如\(\mathbb{Z}_2^5\)(五维布尔向量)下有多少个不同的线性空间?
这样的空间显然不超过C(32,5)个，因为最多5个基向量，每个向量32种选择；进一步地，它不应该超过2^15个，因为行阶梯型要求base数组是5阶上三角01矩阵；实际情况因为行最简形限制会更少；另一方面，它至少大于2^5个，因为不同的列子集一定生成不同的空间。
实际情况384个，我也不知道可不可以算出来。

下面是搜索 \(\mathbb{Z}_2^5\) 所有子空间的代码，出自cf1299d。本题和该代码的巧妙之处在于，由于只有32种向量，我们完全可以用一个uint32表示出整个线性子空间，而不必只存储它的基。搜索空间和合并空间也十分简单。

```
map<ui,int> id; ui state[N]; int ST;
```
```
 
```
```
//search all linear space of Z_2^5
```
```
void dfs_state(ui v){
```
```
	if (id.count(v)) return;
```
```
	id[v]=++ST; state[ST]=v;
```

	for(int i=1;i<32;i++) if (!(v>>i&1)){ //try add vector i

```
		ui w=v;
```
```
		for (int j=0;j<32;j++) //add element 
```
```
			if(v>>j&1) w|=1u<<(i^j); 
```
```
		dfs_state(w);
```
```
	}
```
```
}
```
```
ui meg(ui a, ui b){
```

	//if (!a||!b) return 0; //bad space, already has co-linear

	if ((a>>1)&(b>>1)) return 0; //no intersection

```
	ui ret=0; //direct sum
```
```
	for (int i=0;i<32;i++)
```
```
		for (int j=0;j<32;j++)
```

			if ((a>>i&1) && (b>>j&1)) ret|=1u<<(i^j);

```
	return ret;
```
```
}
```

不是线性基的异或和问题

区间和

有些问题虽然也是异或和，但和线性基无关。例如：
给定一列数字，求异或和最大的区间。

这里要求的是一个区间而不是子集，所以它可能是个数据结构问题，或者说至少和线性基没有半毛钱关系。

要解决上面的问题，首先看一个简单的问题：给一些数，然后每次询问X，求哪个数与X的异或值最大。

显然从高到低位贪心。为了方便查询，只用把给定的数建成0-1 trie。

那么求最大区间的问题也解决了。考虑到xor是其自身的逆运算，设前缀和为S，区间[l,r]异或和即S[l-1] xor S[r]。于是枚举一端查询即可。

区间和的加强

加强版：1、每次询问l,r,x，询问区间内异或x的最大值。 2、除了询问异或和最大的区间，还有在末尾插入新的数。

这两个问题一样，要用到可持久化Trie。

fffasttime

异或和与线性基问题入门

概述

基本操作

线性基的性质

线性基常见模板

加强版

加长

线性基合并，区间和问题

线性空间交

构建全部子空间

不是线性基的异或和问题

区间和

区间和的加强

发表评论取消回复

概述

基本操作

线性基的性质

线性基常见模板

加强版

加长

线性基合并，区间和问题

线性空间交

构建全部子空间

不是线性基的异或和问题

区间和

区间和的加强

发表评论 取消回复

发表评论取消回复