线性基就是，给你n个数，这n个数会有一个线性基，是的n个数异或的任意值（包括这n个数），都可以用这个线性基来异或出来。

线性基大小logn。

然后可以询问异或最大最小值，以及第k大的值

 

洛谷：https://www.luogu.com.cn/problem/P3812

异或第k大：http://acm.hdu.edu.cn/showproblem.php?pid=3949

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int MN = 61; // 代表最高位数
 5 ll a[200];  // a表示线性基
 6 vector<ll> ra; // ra 是rebuild后的改造后线性基
 7 int n;  //总共插入n个数
 8 //两线性基a,b合并就相当于把所有b[i] (b[i] != 0 ) ins到a里面
 9 void ins( ll x){
10     for(int i = MN;i>=0;--i){
11         if( x & 1ll<<i ){
12             if( a[i] ) x ^= a[i];
13             else{
14                 a[i] = x;
15                 break;
16             }
17         }
18     }
19 }
20 //检查这 n 个数能不能选若干个异或成x(1<=x) (x == 0 的话判断ra大小和n关系)
21 bool check( ll x){
22     for(int i = MN;i>=0;--i){
23         if( x & (1ll << i ) ){
24             if( !a[i] ) return 0;
25             else x ^= a[i];
26         }
27     }
28     return 1;
29 }
30 //异或最大值
31 ll qmax(){
32     ll res = 0;
33     for(int i = 61;i>=0;--i) res = max(res,res^a[i]);
34     return res;
35 }
36 //异或最小值
37 // 如果cnt<n 说明n个数不是相互独立,所以0可以异或表示
38 ll qmin(){
39     int cnt = ra.size();
40     if( cnt < n ) return 0;
41     for(int i = 0;i<=MN;++i) if(a[i]) return a[i];
42 }
43 //构建改后线性基
44 void rebuild(){
45     for(int i = 0;i<=MN;++i){
46         for(int j = i-1;j>=0;--j){
47             if( a[i] & (1ll<<j) ) a[i] ^= a[j];
48         }
49         if(a[i]) ra.push_back( a[i] );
50     }
51 }
52 // 第k小
53 ll query( ll k ){
54     int cnt = ra.size();
55     if( cnt < n ) --k;
56     if(!k) return 0;
57     if( k>= (1ll<<cnt) ) return -1;
58     ll res = 0;
59     for(int i = 0;i<ra.size();++i){
60         if( k & (1ll<<i) ) res ^= ra[i];
61     }
62     return res;
63 }
64 int main(){
65     int T; scanf("%d",&T);
66     for(int cas = 1;cas <= T; ++cas){
67         memset(a,0,sizeof(a));
68         ra.clear();
69         printf("Case #%d:\n",cas);
70         scanf("%d",&n);
71         for(int i = 1;i<=n;++i){
72             ll x; scanf("%lld",&x);
73             ins(x);
74         }
75         rebuild();
76         int m; scanf("%d",&m);
77         while(m--){
78             ll k; scanf("%lld",&k);
79             printf("%lld\n",query(k));
80         }
81     }
82     return 0;
83 }

View Code