HDU - 3949 XOR

Posted on | In ,

思路

线性基模板题

线性基

一个向量空间中既是线性无关，同时又能张成该向量空间的向量组V称为向量空间的基。
acm中线性基通常用来计算子集异或问题，如子集最大，最小，第k大异或和，线性基有一个非常重要的性质：

对于任意一个存在于线性基的二进制位，至多只有一个数bj满足第i位为1

也就是说如果我们要选第k大的异或值，我们只要选择k各个二进制位换算成的数在线性基中是第几个数，然后异或一下就是第k大的（因为两两行之间不会出现抵消使得结果变小）。

线性基求法

线性基的求法与线性代数正交基的构造方法——格拉姆-施密特方法非常像，大家可以类比地去学习。
假定我们读入n个数，存放在a[n]，再令b[MAXP]为我们的线性基数列，MAXP为读入数二进制位的最大位数。若我们构造到a[n],我们从高位到低位进行计算。若计算到第j位，我们发现a[i]的二进制位有这个1，那我们看b[j]的基是否已经存在，如果存在，那么我们吧b[j]的影响从a[i]中减掉，表现为b[j]^=a[i],如果不存在，那么我们b[j]=a[i],同时先将比b[j]小的基对b[j]的影响消除，表现为b[j]^=b[k];。对比b[j]大的基，我们要消除b[j]对他们的影响，表现为算法中的b[k]^=b[j]。我们重复计算后就能算出a的线性基。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void build(ll *a,ll n){
    ms(b,0);
    for(int i=0;i<n;i++){
        for(int j=MAXP;j>=0;j--){
            if((a[i]>>j)&1){
                if(b[j])a[i]^=b[j];//eliminate the influence of b[j] in a[i];
                else{
                    b[j]=a[i];
                    for(int k=j-1;k>=0;k--)if(b[k]&&((b[j]>>k)&1))b[j]^=b[k];
                    for(int k=j+1;k<=MAXP;k++)if(b[k]>>j&1)b[k]^=b[j];
                    break;
                }
            }
        }
    }
}

思路

本题是线性基第k小的模板题。思路上问讲过，不过要注意当出现无法插入的值的时候，说明有向量线性相关，所以我们要考虑异或值可以生成0（线性基没有考虑生成0）。

参考

线性基学习笔记

代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
#define INF 0x7fffffff
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

const int MAXN=100000+10,MAXP=62;

struct Linear_Basis{
    ll b[MAXN];
    vector<ll> v;
    int zero;
    void build(ll *a,ll n){
        int cnt=0;//in order to cal the time of update
        ms(b,0);
        for(int i=0;i<n;i++){
            for(int j=MAXP;j>=0;j--){
                if((a[i]>>j)&1){
                    if(b[j])a[i]^=b[j];//eliminate the influence of b[j] in a[i];
                    else{
                        b[j]=a[i],cnt++;
                        for(int k=j-1;k>=0;k--)if(b[k]&&((b[j]>>k)&1))b[j]^=b[k];
                        for(int k=j+1;k<=MAXP;k++)if(b[k]>>j&1)b[k]^=b[j];
                        break;
                    }
                }
            }
        }
        if(cnt<n)zero=1;
        v.clear();
        for(int i=0;i<=MAXP;i++){
            if(b[i])v.push_back(b[i]);
        }
    }
    ll query(ll k){
        if(zero)k--;
        if(k>=(1ll<<(int)v.size()))return -1;
        ll ans=0;
        for(int i=0;i<v.size();i++){
            if((k>>i)&1)ans^=v[i];
        }
        return ans;
    }
}lb;

ll a[100050];
int main() {
    int T,n,m,q;
    ll k;
    scanf("%d",&T);
    for(int z=0;z<T;z++){
        lb.zero=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%I64d",&a[i]);
        lb.build(a,n);
        scanf("%d",&m);
        printf("Case #%d:\n",z+1);
        for(int i=0;i<m;i++){
            scanf("%I64d",&k);
            printf("%lld\n",lb.query(k));
        }
    }
	return 0;
}