[learning notes] linear basis

I still don't feel that I understand qwq …

Definition

Set of assumptions $T$ The range of values is $[1,2^n-1]$ .
$T$ The linear basis of is $T$ One of the A subset of $A=\{a_1,a_2,...,a_n\}$
$A$ All elements in the are mutually xor The XOR set formed , Equivalent to the set of primitive numbers $T$ The elements of each other xor An XOR set formed .
It can be understood as compressing the original number set .

nature

1. The XOR scheme of each element in the XOR set of linear bases only
2. The highest bit of linear basis binary is different from each other
3. Elements in a linear basis are exclusive or to each other , The XOR set does not change .
4. The linear base XOR set size is $2^{|A|}$ , The number of occurrences of each element is exactly $2^{n-|A|}$ .

Insert

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;}
        }
    }
}

nature ： about $n$ A collection of numbers , Suppose the linear basis is $S$ , So it's going to generate $2^{|S|}$ Kind of Different Exclusive or values （ An exclusive or value corresponds to a unique way ）, A value will appear $2^{n-|S|}$ Time .

restructure

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]
	}
} 

Please K Small

According to the nature 2 .
We need to transform the linear basis into each bit independent of each other .
So the query will $K$ Binary split , about $1$ Bit , On the corresponding linear basis on XOR .
The final answer is K Small value .

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;
}

Ranking

Can't . Only ugly code .( There should be some clever way Ha ha ha )

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;
}