牛客180D-xor序列（线性基求存在性）

链接：https://www.nowcoder.com/acm/contest/180/D

来源：牛客网

题目

小a有n个数，他提出了一个很有意思的问题：他想知道对于任意的x, y，能否将x与这n个数中的任意多个数异或任意多次后变为y

输入描述:

第一行为一个整数n，表示元素个数
第二行一行包含n个整数，分别代表序列中的元素
第三行为一个整数Q，表示询问次数
接下来Q行，每行两个数x,y，含义如题所示

输出描述:

输出Q行，若x可以变换为y，输出“YES”，否则输出“NO”

示例1
输入

5
1 2 3 4 5
3
6 7 
2 1
3 8

输出

YES
YES
NO

说明

对于(6,7)来说，6可以先和3异或，再和2异或
对于(2,1)来说，2可以和3异或
对于(3,8)来说，3不论如何都不能变换为8

题意：

给你n个数，q次询问，每次询问给两个数x,y，问x能不能异或上这个n个数中的任意几个变成y

题解：

先对n个数构建线性基，然后可以知道x^a=y,
则有x^y=a,所以只需判断线性基能不能异或出a

代码：

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const int maxn=1e5+7;
const int mod=1e9+7;
struct  Linear_Basis{
    ll b[63],nb[63],tot; //b为线性基 nb用来求第K小异或值 tot为nb元素个数
	bool flag=false;
    void Init(){    //初始化
        tot=0;
		flag=false;
        memset(b,0,sizeof(b));
        memset(nb,0,sizeof(nb));
    }
    void Ins(ll  x){ //插入
        for(int i=62;i>=0;i--){
            if(x&(1ll<<i)){
                if(!b[i]){
                    b[i]=x;
                    return;
                }
                x^=b[i];
            }
        }
		flag=true;
        return;
    }
    bool Fin(ll x){ //验证存在性
        if(x==0&&b[0])return 1;
        for(int i=62;i>=1;i--){
            int j=i-1;
            if(x&(1ll<<j)){
                x^=b[j];
                if(!x)return 1;
            }
        }
        return 0;
    }
}LB;
int main(){
    int n,a,q;
    scanf("%d",&n);
    LB.Init();
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        LB.Ins(a);
    }
    int x,y;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&x,&y);
        x=x^y;
        if(LB.Fin(x))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}