Codeforces 959 F

线性基计数题.

题意： 给定一个序列， $q$q次询问中每次给定 $l$l和 $x$x，问你在序列 $[1,l]$[1,l]中有多少种异或得x
题解： 显然：长度为 $n$n的序列共有 $2^n$2n异或情况。每次在 $[1,l]$[1,l]中判断 $x$x是否存在即可，令 $[1,l]$[1,l]的线性基长度为cnt，则：若 $x$x在 $[1,l]$[1,l]中存在，共 $2^{l-cnt}$2l−cnt种情况（由线性基的性质决定）。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int p[25], a[N], ans[N];
int n, m;

struct Query{
	int l, x, id;
	bool operator < (const Query &A) const {
		return l < A.l;
	}
}q[N];

ll qp(ll a, ll b){
	ll ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

void add(int x) {
	for(int i = 24; i >= 0; i--) {
		if(x >> i & 1) {
			if(!p[i]) {p[i] = x; return ;}
			x ^= p[i]; 
		}
	}
}

void solve(Query A) {
	int l = A.l, x = A.x, id = A.id, cnt = 0;
	for(int i = 24; i >= 0; i--) {
		if(p[i]) {
			cnt++;
			if(x >> i & 1) x ^= p[i];
		}
	}
	
	ans[id] = x ? 0 : qp(2, l - cnt);
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].x), q[i].id = i;
	sort(q + 1, q + 1 + m);
	
	int now = 1;
	
	for(int i = 1; i <= n; i++) {
		add(a[i]);
		while(now <= m && q[now].l == i) solve(q[now]), now++;
	}
	for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
	
	return 0;
}