F. Mahmoud and Ehab and yet another xor task | Codeforces Round #473 (Div. 2)

エディトリアルの通り。j<iまで見てxorsumで作れる集合をSとする。a[i]∈Sのとき、x∈Sであればa[i]⊕∈SなのでSの元はそのままで、各元の構成の仕方が2倍になる。a[i]∉Sのとき、x∈Sならばa[i]⊕x∉Sなので、集合にa[i]⊕xを加えるだけ。|S|が2倍になる。

int main() {
    int N, Q;
    cin >> N >> Q;
    vi A(N);
    rep(i, N)cin >> A[i];

    set<int> S;
    S.insert(0);
    mint val = 1;

    vi L(Q), X(Q);
    vector<vi> qs(N);
    rep(i, Q) {
        cin >> L[i] >> X[i];
        qs[--L[i]].push_back(i);
    }

    vector<mint> ans(Q);
    rep(i, N) {
        if (S.count(A[i])) {
            val *= 2;
        } else {
            set<int> T = S;
            each(x, S)T.insert(x^A[i]);
            S = T;
        }
        each(j, qs[i]) {
            if (S.count(X[j]))ans[j] = val;
        }
    }

    each(a, ans)cout << a << endl;
}