【ybtoj】【線性基】k小異或和

題目

傳送門

解題思路

線性基小知識

三大性質：1.原集合裡的任何數都可以用線性基中某些數的異或和表示

2.線性基中任意數的異或和不等于0

3.線性基的大小隻與原集合有關，大小固定且最小

用數組d存儲線性基

逐一枚舉集合中的元素，并嘗試加入線性基

從高到低枚舉二進制數x的每一位

如果x的第i位是1且d[i]位為空，x成功加入線性基

否則x異或上d[i]（保證d[i]第i位為1，且是最高位）

對于本題，還需對線性基做處理

具體為，枚舉d[i]，若第j位為1，則異或上d[j]

最後還是原集合的線性基

求解過程：假如二進制數k的第i位為1，ans就異或上線性基中第i大的元素，ans即為所求

代碼

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int q,n,m,k,t,p;
long long x,d[100]; 
void add(long long x)
{
	 for (int i=60;i>=0;i--)
	     if (x&(1ll<<i))
	        if (d[i]) x=x^d[i];
	           else {
	           	      d[i]=x;
	           	      break;
			   }
}
long long ask(int k)
{
	 if (k==1&&p<n) return 0;
	 if (p<n) k--;
	 if (k>=(1ll<<p)) return -1;
	 long long ans=0;
	 for (int i=0;i<=60;i++)
	     if (d[i])
	     {
	     	 if (k%2==1) ans^=d[i];
	     	 k/=2;
		 }
	 return ans;
}
int main()
{
	scanf("%d",&q);
    while (q--)
    {
    	  t++,p=0;
    	  scanf("%d",&n);
		  memset(d,0,sizeof(d));
    	  for (int i=1;i<=n;i++)
    	  {
    	      scanf("%lld",&x);
    	      add(x);
          }
          for (int i=1;i<=60;i++)
              for (int j=i-1;j>=0;j--)
                  if (d[i]&(1ll<<j)) d[i]^=d[j];
          for (int i=0;i<=60;i++)
              if (d[i]) p++; 
          scanf("%d",&m);
          printf("Case #%d:\n",t);
          for (int i=1;i<=m;i++)
          {
          	   scanf("%d",&k);
          	   printf("%lld\n",ask(k));
		  }
	}
	return 0;
}