【codeforces959F】Mahmoud and Ehab and yet another xor task（线性基）

题意：
给定一个序列a，每次询问给出$l$,$x$,询问前$l$个数中异或和为$x$的方案数
题解：
设集合$V$的线性基为$\beta$
对于线性基可以表示的所有的数，出现次数都是$2^{|V|-|\beta|}$
从前往后不断加入时,不同的线性基不会超过$log(a_{max})$个，所以只需要预处理所有前缀的线性基就可以做到$O(log)$的在线查询

//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf=(1<<30);
inline LL in()
{char ch=getchar();LL f=1,tmp=0;while(ch<'0'||ch>'9') {
   if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}return tmp*f;
}const int mod=1e9+7;
const int N=100010;
int n,m;
LL a[N],mi[N];struct LB
{LL a[61],cnt;bool ins(LL x){for(int i=60;i>=0;i--) if(x&(1ll<<i)){if(!a[i]) {a[i]=x;cnt++;break;}x^=a[i];}return x>0;}
}Xor[100];LL query(const LB &c,LL x,int p)
{for(int i=60;i>=0;i--)if(x&(1ll<<i)){if(!c.a[i]) return 0;x^=c.a[i];}if(x>0) return 0;return mi[p-c.cnt];
}int tot,bel[N];int main()
{n=in();m=in();mi[0]=1;for(int i=1;i<N;i++) mi[i]=mi[i-1]*2%mod;for(int i=1;i<=n;i++){LL x=in();LB cur=Xor[tot];if(cur.ins(x)) Xor[++tot]=cur;bel[i]=tot;}for(int i=1;i<=m;i++){LL l=in(),x=in();printf("%I64d\n",query(Xor[bel[l]],x,l));}return 0;
}