HDU 3949 XOR 高斯消元

HDU 3949 XOR 高斯消元

題目大意：給定一個數組，求這些數組通過異或能得到的數中的第k小是多少

首先高斯消元求出線性基，然後將k按照二進制拆分即可

注意當高斯消元結束後若末尾有0則第1小是0 特判一下然後k--

然後HDU輸出long long是用%I64d 無論C艹還是G艹都是

#include
#include
#include
#include
#define M 10100
using namespace std;
typedef long long ll;
int n,m,cnt;
bool zero;
ll a[M];
void Gaussian_Elimination()
{
	int i,k=0;
	ll j;
	for(j=1ll<<62;j;j>>=1)
	{
		for(i=k+1;i<=n;i++)
			if(a[i]&j)
				break;
		if(i==n+1)
			continue;
		swap(a[i],a[++k]);
		for(i=1;i<=n;i++)
			if(i!=k)
				if(a[i]&j)
					a[i]^=a[k];
	}
	zero=(k!=n);
	n=k;
}
ll Query(ll x)
{
	int i;
	ll re=0;
	x-=zero;
	if(!x)
		return 0;
	for(i=n;i;i--)
	{
		if(x&1)re^=a[i];
		x>>=1;
	}
	if(x)
		return -1;
	return re;
}
int main()
{
	int T,i;
	ll x;
	for(cin>>T;T;T--)
	{
		printf("Case #%d:\n",++cnt);
		cin>>n;
		for(i=1;i<=n;i++)
			scanf("%I64d",&a[i]);
		Gaussian_Elimination();
		cin>>m;
		for(i=1;i<=m;i++)
			scanf("%I64d",&x),printf("%I64d\n", Query(x) );
	}
}