LOJ114_k 大异或和_线性基

LOJ114_k 大异或和_线性基

---

先一个一个插入到线性基中，然后高斯消元。

求第K小就是对K的每一位是1的都用对应的线性基的一行异或起来即可。

但是线性基不包含0的情况，因此不能确定能否组成0，需要特判。

在插入一个数时如果这个数最后变成0了就说明可以组成0.

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

ll b[55];

int flg;

void insert(ll x) {

	int i;

	for(i=50;i>=0;i--) {

		if(x&(1ll<<i)) {

			if(b[i]) x^=b[i];

			else {b[i]=x; return ;}

		}

	}

	if(!x) flg=1;

}

void Guass() {

	int i,j;

	for(i=50;i>=0;i--) {

		if(b[i]) {

			for(j=50;j>=0;j--) {

				if(i!=j&&(b[j]&(1ll<<i))) {

					b[j]^=b[i];

				}

			}

		}

	}

}

int main() {

	int n,m;

	scanf("%d",&n);

	int i;

	ll x;

	for(i=1;i<=n;i++) scanf("%lld",&x),insert(x);

	Guass();

	int cnt=0;

	for(i=0;i<=50;i++) {

		if(b[i]) b[cnt++]=b[i];

	}

	scanf("%d",&m);

	while(m--) {

		scanf("%lld",&x);

		if(x>(1ll<<cnt)) {

			puts("-1"); continue;

		}

		x-=flg;

		ll ans=0;

		for(i=cnt;i>=0;i--) {

			if(x&(1ll<<i)) ans^=b[i];

		}

		printf("%lld\n",ans);

	}

}