K小异或和 / XOR

题目链接： /

题目大意

给你一些数，你可以任意选数异或。 问你能异或出的数字中第 k 小的那个。

思路

看到异或，自然想到线性基。

但接着问题是如何找。 我们已经可以确定，如果线性基的第 i i i 个数不是 0 0 0，那构造出的数就可以选二进制第 i i i 位是 1 / 0 1/0 1/0。 但由于线性基别的数二进制第 i i i 位可能是 1 1 1，那我们无法很好的搞出保证第 i i i 位是 1 1 1 的数。

那我们考虑改造我们的线性基。（线性基不是唯一的） 那我们从大到小枚举 p i p_i pi，然后再从 i − 1 i-1 i−1 到 0 0 0 枚举 j j j，如果 p i p_i pi 的第 j j j 为是 1 1 1，我们就把它异或上 p j p_j pj。 这样，我们就构造出了新的线性基，它大概是这个样子的。

1xxx0xxxxx0x0
00001xxxxx0x0
00000000001x0
0000000000001

那就可以愉快的搞了。 但搞的时候你会发现一个问题，原本数可能会异或出 0 0 0，但你从线性基中难以通过异或找到。 那你想，如果不能异或出 0 0 0，那每个数最终都会在线性基中被插入。 那我们可以记线性基中不为 0 0 0 的数的个数是 t o t tot tot，那如果 t o t = n tot=n tot=n，那所有数都被插入，不能异或出 0 0 0，否则就可以异或出 0 0 0。

那接着就是搞。 具体就是你把 k k k 弄成二进制，如果第 i i i 位是 1 1 1，那就要异或上线性基中从小到大第 i i i 个不是 0 0 0 的数。

然后记得如果能构造出 0 0 0 的话 k k k 要减去 1 1 1（表示减去 0 0 0 这一种，当然如果减了之后 k = 0 k=0 k=0 就说明要的就是 0 0 0） 还有就是可能没有第 k k k 小的数字，那其实就是构造出的数没有 k k k 个。 那就是 2 t o t − 1 < k 2^{tot}-1<k 2tot−1<k。

代码

#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

int T, n, tot, q, tmp;
ll p[101], x;

void csh() {
          
   
	memset(p, 0, sizeof(p));
	tot = 0;
}

void add(ll x) {
          
   //构造线性基
	for (int i = 60; i >= 0; i--)
		if ((x >> i) & 1) {
          
   
			if (!p[i]) {
          
   
				p[i] = x;
				break;
			}
			x ^= p[i];
		}
}

void work() {
          
   //弄出新的线性基
	for (int i = 60; i >= 0; i--)
		if (p[i]) {
          
   
			tot++;
			for (int j = i - 1; j >= 0; j--)
				if ((p[i] >> j) & 1)
					p[i] ^= p[j];
		}
}

ll kth_small(ll k) {
          
   //查询第 k 小
	if (tot != n) k--;//有 0
	if (k == 0) return 0;//找的就是 0
	if (k >= (1ll << tot)) return -1;//构造不出那么多的数
	
	ll re = 0;
	for (int i = 0; i <= 60; i++)
		if (p[i]) {
          
   
			if (k & 1) re ^= p[i];
			k >>= 1;
		}
	
	return re;
}

int main() {
          
   
	scanf("%d", &T);
	while (T--) {
          
   
		csh();
		printf("Case #%d:
", ++tmp);
		
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
          
   
			scanf("%lld", &x);
			add(x);
		}
		
		work();
		
		scanf("%d", &q);
		while (q--) {
          
   
			scanf("%lld", &x);
			printf("%lld
", kth_small(x));
		}
	}
	
	return 0;
}