题目链接

题目描述

小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

备注:

对于100%的数据，n,Q<=10^5
保证所有运算均在int范围内

题意

如题，判断一个数能否被当前线性基中的元素异或得到,q次查询

思路

关于线性基

向量空间的基：向量空间中最大的线性无关组成为该向量空间的一组基

线性基：一般指模2空间（异或）下的一个子空间的基

应用范围：求一个集合S中取一个子集异或得到所有数的数量；求一个集合S中取一个子集异或可以得到的最大/小值

关于异或的小性质：

如果a ^ b ^ c == 0，则a ^ b == c;

如果a ^ b == c，则a ^ c == b;

线性基的性质之一：原序列里面的任意一个数都可以由线性基里面的一些数异或得到

所以尝试把得到的数插到线性基里面去，如果可以插入说明不能异或得到，如果插不进去说明可以异或得到

（初学，记录很板子的操作）

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define PII pair<int,int>
#define endl '\n'
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
const double pi = acos(-1.0);
typedef long long ll;
int t, n, m;
int base[65];//最高位为第i位的基
void insert(int x) {
	for (int i = 32; i >= 0; i--) {
		if (x & (1ll << i)) {//如果i大于31,1后面要加ll
			if (!base[i]) {
				base[i] = x;
				return;
			}
			x ^= base[i];
		}
	}
}
int find(int x) {
	for (int i = 32; i >= 0; i--) {
		if (x & (1ll << i)) {
			if (!base[i]) return 0;
			x ^= base[i];
		}
	}
	return 1;
}
void init() {
	for (int i = 0; i <= 64; i++) {
		base[i] = 0;
	}
	return;
}
void solve() {
	init();
	int x, y;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		insert(x);
	}
	int q;
	cin >> q;
	while (q--) {
		cin >> x >> y;
		if (find(x ^ y)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	while (cin >> n) {
		solve();
	}
	return 0;
}