E题

E题
用线性基和二分来写
找到第一个大于k的数的位置
再用总数减一下就可以了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll d[100],p[100],k,a;
int n,cnt;
bool f=0;
void insert(ll x){
    for(int i=62;i>=0;i--)
    if(x&(1ll<<i))
    {
        if(d[i])x^=d[i];
        else{d[i]=x;return;}
    }
    f=1;
}
void rebuild(){
    for(int i=62;i>=1;i--)
    for(int j=i-1;j>=0;j--)
    if(d[i]&(1ll<<j))d[i]^=d[j];
    for(int i=0;i<=62;i++)
    if(d[i])p[cnt++]=d[i];
}
ll getkth(ll k){
    if(f)--k;
    if(!k)return 0;
    if(k>=(1ll<<cnt))return -1;
    ll ans=0;
    for(int i=0;i<cnt;i++)
    if(k&(1ll<<i))ans^=p[i];
    return ans;
}
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&a),insert(a);
    rebuild();
    ll l=1,r=(1ll<<cnt)+f-1;
    while(l<r)
    {
        ll m=l+r>>1;
        if(getkth(m)>k)r=m;
        else l=m+1;
    }
    cout<<(1ll<<cnt)-l+f<<endl;//由于线性基得不到0所以f用来表示0存不存在
    return 0;
}