题意:长度为n的序列,q个查询,每次查询一个l,x问[1, l]中子序列异或出来等于x的个数
题解:这道题可以用线性基来处理
线性基是一个集合,它异或出来的集合与原集合异或相同
原集合异或出来的数可以由线性基唯一表示
一个数能遍历线性基得到0,这个数就可以被异或出来
那么这道题可以离线处理,对于每一个查询[l ,x],已经处理出来[1, l]的线性基,那么遍历一遍后可以知道x能否表示
计算个数的时候,因为一个线性基代表一个数,所以遍历后的num就是表示x所需要的数,而剩下的l-num个数,如果可以表示为y,那么这l个数就一定可以表示出y^x(因为前面是已经判断过x一定给可以表示)
所以答案就是2^(l-num)
#include#define maxn 100010#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;int num;struct L_B{ ll d[61],p[61]; int cnt; L_B() { memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); cnt=0; } bool insert(ll val) { for (int i=60;i>=0;i--) if (val&(1LL< 0; } ll query_max() { ll ret=0; for (int i=60;i>=0;i--) if ((ret^d[i])>ret) ret^=d[i]; return ret; } ll query_min() { for (int i=0;i<=60;i++) if (d[i]) return d[i]; return 0; } void rebuild() { for (int i=60;i>=0;i--) for (int j=i-1;j>=0;j--) if (d[i]&(1LL< =(1LL< =0;i--) if (k&(1LL< =0;i--){ if(d[i]){ num++; if(x&(1LL< =0;i--) if (n2.d[i]) ret.insert(n1.d[i]); return ret;}ll f(ll a,ll b){ ll mod = 1e9+7; a %= mod; ll ans = 1; while(b){ if(b&1) ans = ans*a%mod; a = a*a%mod; b >>= 1; } return ans;}ll a[maxn], ans[maxn], l, x;vector >G[maxn];int main(){ ll n, q; cin>>n>>q; for(int i=1;i<=n;i++) scanf("%lld", &a[i]); for(int i=1;i<=q;i++){ scanf("%lld%lld", &l, &x); G[l].push_back(make_pair(i, x)); } for(int i=1;i<=n;i++){ b.insert(a[i]); for(auto j:G[i]){ if(b.query(j.second)) ans[j.first] = f(2, (i-num)); } } for(int i=1;i<=q;i++) cout< <