ex模板

Posted on | Edited on | In | Views:

线性基

线性基是一个数的集合，并且每个序列都拥有至少一个线性基。

性质

  1. 原序列里面任意一个（一些数异或和）都可以由线性基里面的一些数异或得到，同时，线性基里面的任意一个数也可以由原序列里面的一些数异或得到。
  2. 线性基里面的任意一些数异或起来都不能得到 $0$
  3. 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
ll d[100];//线性基，若 d[i]>0，d[i]二进制的第i位一定为1
bool add(ll x){//添加元素
    for(int i=63;i>=0;i--){
    	if(x&(1ll<<i)){
    		if(d[i])x^=d[i];
    		else{
    			d[i]=x;
    			return 1;
    		}
    	}
    }
    return 0;
}

最大最小

1
2
3
4
5
6
7
8
9
10
11
12
ll MAX(){//求在原序列中，取若干个数，使得其异或和最大
    ll ans=0;
    for(int i=63;i>=0;i--)
        if((ans^d[i])>ans)ans^=d[i];
	return ans;
}
ll MIN(){//求在原序列中，取若干个数，使得其异或和最小
    for(int i=0;i<64;i++){
        if(d[i])return d[i];
    }
    return 0;
}

第k大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int cnt;
ll p[100];
void work(){//预处理，使得若 d[i]>0，其他d[j]二进制的第i位一定为i，不会影响线性基的正确性
    for(int i=1;i<=63;i++)   
    for(int j=0;j<i;j++)
		if(d[i]&(1ll<<j))d[i]^=d[j];
    cnt=0;
	for(int i=0;i<=63;i++)
        if(d[i])p[cnt++]=d[i];
}
ll k_th(ll k){//将k先转成二进制，假如k的第i位为1，ans就异或上线性基中第i个元素（注意不是直接异或d[i-1]
    if(k>=(1ll<<cnt))return -1;
    work();
    ll ans=0;
    for(int i=0;i<cnt;i++)
        if(k&(1ll<<i))ans^=p[i];
	return ans;
}