线性基模板

Posted on | In ,

​ 线性基类似于线性代数中的基向量，我们找一个整数集的线性基，实际上是找这样一个集合P，使得P中的元素互相异或运算得到的结果集和原集合相等。从二进制上看，最终我们期望得到

​ 1—–

​ 01—

​ 001-

这样的集合，同时也可以进一步将低位的0消去。

向原集合插入一个新数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void inst(ll a){
    for(int i=61;i>=0;i--){
        if(a&(1ll<<i)){
            if(!p[i]){
                p[i]=a;
                break;
            }else{
                a^=p[i];
            }
        }
        if(a==0){
            //可以异或出0,会导致cnt比N小
            break;  //简单优化
        }
    }
}

询问第K大（线性基的值域第k大）

原理从二进制上看很直观，从小到大每个基有选与不选两种选择，将K看作二进制数，选取1位置的基即可，如果线性基能产生0则将k减1。

询问第k大的时候需要你把每个线性基的低位都清除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll query(ll k){	//要求线性基已经整理成对角矩阵的形式
    if(cnt<N)	//结果集包含0
        k--;	//把0的次序去掉
    ll res=0;
    for(int i=0;i<=61;i++){
        //这个循环顺序无所谓
        if((k>>i)&1){
            if(rk[i]==-1)   //还没有这个基
                return -1;
            res^=p[rk[i]];  //rk标记第i个基的下标,其实应该是rk的逆映射（
        }
    }
    return res;
}

询问第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
41
42
43

...

int T,N,Q;
ll p[62],rk[62];	//p[i]表示2^i的基
int cnt;

...
    
int main(){
    cin>>T;
    for(int cse=1;cse<=T;cse++){
        memset(rk,-1,sizeof(rk));
        memset(p,0,sizeof(p));
        cnt=0;

        cin>>N;
        ll x;
        for(int i=0;i<N;i++){
            cin>>x;
            inst(x);
        }
        for(int i=0;i<=61;i++){
            if(p[i])
                rk[cnt++]=i;
        }
        for(int i=1;i<=61;i++){     //清除低位1
            for(int j=0;j<i;j++){
                if((1ll<<j)&p[i])
                    p[i]^=p[j];
            }
        }

        cin>>Q;
        cout<<"Case #"<<cse<<":\n";
        while(Q--){
            ll k;
            cin>>k;
            cout<<query(k)<<'\n';
        }
    }
    return 0;
}