Loj 114 k大异或和

时间：2024-11-25 15:35:02

Loj 114 k大异或和

  • 构造线性基时有所变化.试图构造一个线性基,使得从高到低位走,异或上一个非 \(0\) 的数,总能变大.
  • 构造时让任意两个 \(bas\) 上有值的 \(i,j\) ,满足 \(bas_i\) 的第 \(j\) 位为 \(0\) ,这样就可以使得从高往低走异或上当前数一定变大.
  • 那么最大的方案就是每一位都异或,第 \(k\) 大的方案只需要根据 \(k\) 的二进制拆分判一下每一位是否异或就可以了.
  • 注意如果这个基底向量组是满秩的,那么 \(0\) 就无法异或出,需让 \(k=k+1\) .
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

	ll out=0,fh=1;

	char jp=getchar();

	while ((jp>'9'||jp<'0')&&jp!='-')

		jp=getchar();

	if (jp=='-')

		fh=-1,jp=getchar();

	while (jp>='0'&&jp<='9')

		out=out*10+jp-'0',jp=getchar();

	return out*fh;

}

const int MAXD=50,MAXN=1e5+10;

ll bas[MAXD+10];

int n,rank=0;

void ins(ll x)

{

	for(int i=MAXD; i>=0; --i)

		{

			if((x>>i) & 1LL)

				{

					if(!bas[i])

						{

							bas[i]=x;

							++rank;

							for(int j=i-1; j>=0; --j)

								if((bas[i]>>j) & 1LL)

									bas[i]^=bas[j];

							for(int j=i+1; j<=MAXD; ++j)

								if((bas[j]>>i) & 1LL)

									bas[j]^=bas[i];

							break;

						}

					else

						x^=bas[i];

				}

		}

}

ll solve(ll k)

{

	if(rank==n)

		++k;

	if(k> (1LL<<rank) )

		return -1;

	ll ans=0;

	int mxd=rank-1;

	for(int i=MAXD;i>=0;--i)

		{

			if(!bas[i])

				continue;

			if(k>(1LL<<mxd))

				ans^=bas[i],k-=1LL<<mxd;

			--mxd;

		}

	return ans;

}

int main()

{

	n=read();

	for(int i=1; i<=n; ++i)

		ins(read());

	int m=read();

	while(m--)

		{

			ll k=read();

			printf("%lld\n",solve(k));

		}

	return 0;

}

相关文章