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; }