HDU 3949 XOR

发表于 | 更新于

Link

Solution

想写一道第KK大XOR的题，找到之后开始写发现，写着写着发现熟悉的触目惊心。。翻提交记录，果然早就把这道题A了。。23333 做法就是处理线性基，然后把KK二进制拆分，在11的位上异或上相应位的线性基。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define getf(x) scanf("%lf",&x)
#define gets(x) scanf("%s",x)
#define getl(x) scanf("%lld",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
const int MAXN=10000+11,LEN=63;
LL a[MAXN];int n;
using std::find_if;
using std::swap;

int __bit;bool Exist(LL x){return x>>__bit&1;}
bool gotzero;
void Basis()
{
    int p=0;
    for(int j=LEN;~j;j--)
    {
        int l;
        if((l=(__bit=j,find_if(a+1+p,a+1+n,Exist)-a))==n+1) continue;
        swap(a[++p],a[l]);
        for(int i=1;i<=n;i++)
            if(i!=p && (a[i]>>j&1)) a[i]^=a[p];
    }
    gotzero=(p!=n);
    n=p;

}
LL Query(LL k)
{
    if(gotzero) k--;
    LL res=0;
    for(int i=n;i;i--)
    {
        if(k&1) res^=a[i];
        k>>=1;
    }
    if(k) return -1;
    return res;
}
void WORK()
{
    get(n);
    for(int i=1;i<=n;i++) getl(a[i]);
    Basis();
    int Q;get(Q);
    for(int i=1;i<=Q;i++)
    {
        LL k;getl(k);
        printf("%lld\n",Query(k));
    }
}
int main()
{
    int T;get(T);
    for(int t=1;t<=T;++t)
        printf("Case #%d:\n",t),WORK();
    return 0;
}