柒葉灬 的博客

柒葉灬 的博客

线性基

posted on 2019-05-19 14:55:59 | under 算法学习 |

线性基


如果一个序列 $A$ ,可以亦或出来的集合为 $S$ ,

那么存在一个序列 $B$ ,使得能亦或出来的集合为 $S$ 。

$B$ 序列中的数个数是 $log_2Max\{A_i\}$


线性基求第K大。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e4+100;
int n;
long long a[65];
bool insert(long long p){
    for(int i=62;i>=0;i--){
        if(p>>i&1){
            if(a[i])p^=a[i];
            else {
                for(int j=i-1;j>=0;j--)
                    if(p>>j&1)p^=a[j];
                for(int j=i+1;j<=62;j++)
                    if(a[j]>>i&1)a[j]^=p;
                a[i]=p;
                return false;
            }
        }
    }
    return true;
}
int id,num[65];
int main(){
    for(int cas=1,_=(cin>>_,_);cas<=_;cas++){
        scanf("%d",&n);

        bool isok=0;
        memset(a,0,sizeof(a));

        for(int i=1;i<=n;i++){
            long long x;
            scanf("%lld",&x);
            isok|=insert(x);
        }
        id=0;
        for(int i=0;i<=62;i++)
            if(a[i])num[id++]=i;
        printf("Case #%d:\n",cas);
        for(int q=(cin>>q,q);q--;){
            long long K;
            scanf("%lld",&K);
            K-=isok;
            if(K==0)puts("0");
            else if(K>=(1LL<<id))puts("-1");
            else{
                long long ans=0;
                for(int i=0;i<=62;i++)
                    if(K>>i&1)ans^=a[num[i]];
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}