959F - Mahmoud and Ehab and yet another xor task - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9+7;
const int N = 1e5+5, D = 20;

ll p2[N];

void solve() {
  int n, q;  cin >> n >> q;
  vector<int> a(n);
  for (auto &ai: a) {
    cin >> ai;
  }
  vector<array<int, 2>> cu[n];
  for (int i = 0; i < q; ++i) {
    int l, x;  cin >> l >> x;  l--;
    cu[l].push_back({x, i});
  }
  vector<int> basis(D);
  int rank = 0;
  vector<int> ans(q);
  for (int i = 0; i < n; ++i) {
    int mask = a[i];
    for (int j = D - 1; j >= 0; --j) {
      if (!(mask & (1 << j)))  continue;
      if (!basis[j]) {
        basis[j] = mask;
        rank++;
        break;
      }
      mask ^= basis[j];
    }

    for (auto [x, idx]: cu[i]) {
      for (int j = D - 1; j >= 0; --j) {
        if (!(x & (1 << j)))  continue;
        x ^= basis[j];
      }
      if (x == 0) {
        ans[idx] = p2[i - rank + 1];
      }
    }
  }

  for (auto x: ans) {
    cout << x << "\n";
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);

  p2[0] = 1;
  for (int i = 1; i < N; ++i) {
    p2[i] = p2[i - 1] + p2[i - 1];
    if (p2[i] >= mod)  p2[i] -= mod;
  }

  int tc = 1;
  for (int t = 1; t <= tc; ++t) {
    solve();
  }
}