线性基第k小
作者:
流动的音符
,
2024-10-22 19:45:06
,
所有人可见
,
阅读 9
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200;
int a[maxn];
int dp[maxn];///线性基
int dp1[maxn];///改造线性基
int cnt=0,n,k;///cnt代表线性基的元素个数,
void insert_num(int x)///初始线性基
{
for(int i=61; i>=0; i--)
{
if(x&(1ll<<i))
{
if(dp[i])
x^=dp[i];///保证每个位置元素的唯一性
else
{
dp[i]=x;
break;
}
}
}
}
void exchange()///改造线性基
{
for(int i=0; i<=61; i++)
{
for(int j=i-1; j>=0; j--)
if(dp[i]&(1ll<<j))///其他位变成0,保证唯一性
dp[i]^=dp[j];
if(dp[i])
dp1[cnt++]=dp[i];
}
}
int min_k_num(int k)///求第K小
{
int ans=0;
for(int i=0; i<cnt; i++)
{
if((k>>i)&1)
ans^=dp1[i];
}
return ans;
}
signed main()
{
cin>>n>>k;
for(int i=1; i<=n; i++)
{
int x;cin>>x;
insert_num(x);
}
exchange();
int max_knum=(1<<cnt);//线性基产生的最大元素个数
if(cnt<n&&k==1)//最小的就是0
cout<<"0"<<endl;
else
{
if(cnt<n)//减去0
k--;
if(max_knum<k)//产生的数小于k
cout<<"-1"<<endl;//无法产生
else
cout<<min_k_num(k)<<endl;
}
return 0;
}