出题人题解 | #xor序列#

原题解链接：https://ac.nowcoder.com/discuss/149980

性质: 若 $x\oplus z=y,x\; \backslash oplus\; z=y,\; \backslash quad$ 则 $x\oplus y=zx\; \backslash oplus\; y=z$

考虑答案一定是 $x\oplus \{x\; \backslash oplus\backslash \{$ 坨东西 $\}=y\backslash \}=y$

那么 $x\oplus y=\{x\; \backslash oplus\; y=\backslash \{$ 一坨东西 $\}\backslash \}$

因此问题变为询问序列中是否有 $x\oplus yx\; \backslash oplus\; y$

->线性基经典操作

时间复杂度: $O(n\log n)O(n\; \backslash log\; n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long 
using namespace std;
const LL MAXN = 32, B = 31;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL N;
LL P[MAXN];
void Insert(LL x) {
    for(LL i = B; i >= 0; i--) {
        if((x >> i) & 1) {
            if(!P[i]) {P[i] = x; break;}
            x ^= P[i];
        }
    }
}
LL Query(LL x) {
    for(LL i = B; i >= 0; i--) {
        if((x >> i) & 1) {
            if(!P[i]) return 0;
            x ^= P[i];
        }
    }
    if(x == 0) return 1;
    else return 0;
}
int main() { 
    N = read();
    for(LL i = 1; i <= N; i++) {
        LL val = read(); Insert(val);
    }
    LL Q = read();
    while(Q--) {
        LL x = read(), y = read();
        if(Query(x ^ y)) puts("YES");
        else puts("NO");
    }
}