HDU-3949 XOR 题解报告

题目地址

题意：

从一个序列中取任意个元素进行异或，求能异或出的所有数字中的第 k 小。

分析：

性质：一个线性基异或上另一个不同的线性基，并作为自己的新值，这并不改变整个线性基的性质（线性基只有元素数量是固定的）。

从大到小枚举每一个线性基d[i]，从它的第二高位往低位扫，如果扫到d[i]在第j位是1，那么就异或上d[j]（d[j]最高位是1），这样就消去d[i]在第j位上的1。当然d[ j ]这个向量可能不存在。那么原本该位的1不变。那么处理完一个线性基之后，应该大致是长这个样子的（x表示0或1）：

   1xxxx0xxx0x
        1xxx0x
            1x

也就是，每个线性基元素的最高位1，只会由自己贡献，这依旧满足线性基基本性质。我们把这些新元素放入新数组_base，无视旧数组中的空向量，记新数组大小为cnt。_base数组具有与二进制基数一样特点：

1. 每个向量选或不选；
2. 往一个集合中加入新向量，或者把集合中一个元素换做更大的向量，集合异或和会变大；
3. 比向量X小的所有向量的异或和，仍小于X。

如果k的第 i 位为1，那么结果就异或上 _base[i]，最后便得到了第 k 小。

额外补充：

给予一组元素，每个数互异且遍布了2的幂，即 \(2^0,2^1,2^2,2^3,2^4...\)。定义一个集合的大小为这个集合中的元素之和，我们想知道在上述序列中，第k小的子集的大小。很显然，这个第k小子集的大小就是 k 本身。比如k是(1001)，结果便是（\(2^0+2^3\)）。

如果我们去掉某些权位，比如得到 \(2^0,\_\ ,2^2,2^3,\_\ ,2^5,...\)，再询问第k小。那么，对于序列的所有子集的值，在二进制表示下，位权缺失的位都为0，无视这些位后仍可视作二进制数。于是我们可以直接剔除缺失部分，以其他数代位。对于k是(1001)，结果便为（\(2^0+2^5\)）。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	int T;
	cin>>T;
	for(int NO=1;NO<=T;++NO)
	{
		cout<<"Case #"<<NO<<":\n";
		ll base[65] = {0};
		int zero=0;
		int n;
		cin>>n;
		for(int i=1;i<=n;++i)
		{
			ll x;
			cin>>x;
			for(int j=63;j>=0;--j)
			{
				if(x>>j)
				{
					if(base[j])
						x^=base[j];
					else{
						base[j]=x;
						break;
					}
				}
			}
			if(x==0)
				zero=1;
		}
		vector<ll> b;
		for(int i=63;i>=0;--i)
		{
			if(!base[i])
				continue;
			for(int j=i-1;j>=0;--j)
			{
				if((base[i]>>j)&1)
				{
					base[i]^=base[j];
				}
			}
			b.push_back(base[i]);
		}
		reverse(b.begin(),b.end());
		int m = b.size();
		int q;
		cin>>q;
		while(q--)
		{
			ll k;
			cin>>k;
			if(k>=(1LL<<m)+zero)
			{
				cout<<"-1\n";
				continue;
			}
			k-=zero;
			ll ans=0;
			for(int i=0;i<64;++i)
			{
				int r=((k>>i)&1);
				if(r)
					ans^=b[i];
			}
			cout<<ans<<"\n";
		}
	}
}