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; }