[牛客竞赛]Xor序列（线性基 + 数学）

题目传送门：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;
}