题目传送门:H-xor序列
思路 / Thought
求线性基然后判断x ^ y能否被线性表示即可,因为若x ^ z = y则有z = x ^ y也就是说线性基能够表示x ^ y。
关于线性基参考这篇文章《[数学基础 & 模板]Xor Linear Basis异或线性基学习笔记》
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 70, MAXL = 63; int p[maxn], d[maxn], tot, N; void ins(int x) { for(int i = MAXL;i >= 0; -- i)//Traverse from back to front { if(!x)return; if(!(x >> i & 1))continue; if(p[i])x ^= p[i]; else return p[i] = x, void(); } } void rebuild() { tot = 0; for(int i = 0;i <= MAXL; ++ i) { for(int j = 0;j < i; ++ j)if(p[i] >> j & 1)p[i] ^= p[j]; if(p[i])d[tot ++] = p[i];//the idx of d is from 0 to (tot - 1) } } bool isok(int x) { for(int i = MAXL;i >= 0; -- i) { if(!(x >> i & 1))continue; if(p[i])x ^= p[i]; else return false;//the x could not be represented by Linear Basis } return true;//could } signed main() { ios::sync_with_stdio(0); cin >> N;//the count of elements for(int i = 1;i <= N; ++ i) { int x;cin >> x; ins(x);//insert x into the Linear Basis } rebuild();//do not forget to rebuild int M;cin >> M;//M is the count of query while(M --) { int x, y;cin >> x >> y; cout << (isok(x ^ y) ? "YES" : "NO") << '\n'; } return 0; }
Comments NOTHING