【学习笔记】线性基

感觉还是没太搞懂 qwq …

定义

设数集 $T$ 的值域范围为 $[1,2^n-1]$ 。
$T$ 的线性基是 $T$ 的一个 子集 A = { a 1 , a 2 , . . . , a n } A=\{a_1,a_2,...,a_n\} A={a1​,a2​,...,an​}
$A$ 中所有元素互相 xor 所形成的异或集合，等价于原数集 $T$ 的元素互相 xor 形成的异或集合。
可以理解为将原数集进行了压缩。

性质

1. 线性基的异或集合中每一元素的异或方案 唯一
2. 线性基二进制最高位互不相同
3. 线性基中元素互相异或，异或集合不变。
4. 线性基异或集合大小为 $2^{|A|}$ ，每种元素出现次数恰为 $2^{n-|A|}$ 。

插入

void ins(int x) {
    for(int i=50;i>=0;i--) {
        if(x>>i&1) {
            if(a[i]) x^=a[i];
            else {a[i]=x;return;}
        }
    }
}
1
2
3
4
5
6
7
8

性质：对于 $n$ 个数的集合，假设线性基为 $S$ ，那么会生成 $2^{|S|}$ 种 不同 的异或值 （一种异或值对应唯一的方式），一个值会出现 $2^{n-|S|}$ 次。

重构

void rebuild() {
	for(int i=50;i>=0;i--) {
	    for(int j=i-1;j>=0;j--) {
	        if(a[i]>>j&1) a[i]^=a[j];
	    }
	}
	for(int i=0;i<=50;i++) {
		if(a[i]) p[cnt++]=a[i]
	}
} 
1
2
3
4
5
6
7
8
9
10

求第 K 小

根据性质 2 。
我们要将线性基改造成每一位相互独立。
所以查询的时候将 $K$ 二进制拆分，对于 $1$ 的位，就异或上对应的线性基。
最终得出的答案就是 K 小值。

void Kth(ll K) {
	K--;
	if(K>=(1<<cnt)) return -1;
	ll res(0);
	for(int i=0;i<cnt;i++) {
	    if(K>>i&1) res^=p[i];
	}
	return res;
}
1
2
3
4
5
6
7
8
9

求排名

不会。只能献上丑丑的代码。(应该有什么巧妙的方法吧 哈哈哈)

ll qry(int x) {
    ll res(0),y(0);
    for(int i=30;i>=0;i--) {
        if(a[i]==0) {
            if((y>>i&1)>(x>>i&1)) {
                break;
            }
        }
        else {
            if(x>>i&1) {
                res=(res+fpow(2,(i>0)?cnt[i-1]:0,10086))%10086;
            }
            if((x>>i&1)!=(y>>i&1)) {
                y^=a[i];
            }
        }
    }
    if(y<x) res++;
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20