https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_f
こういうの最近Codeforcesでも見た。
とりあえずdpを書いてみます。
dp[i][a]:=要素iまで見た時xor sumがaになるものの場合の数。
これはO(NK)になってとても間に合いませんが、iを固定して良くみるとdp[i][a]は0またはある値しかとりえません。
なのである値ansとansを取るものの集合Sを管理すればO(KlogK+N)で求められます。
int N, K; bool S[MAX_N * 2]; void solve() { cin >> N >> K; ll ans = 1; S[0] = 1; rep(i, 0, N) { ll a; cin >> a; if(!S[a]) { rep(i, 0, (1 << 17)) { if(S[i]) { S[i ^ a] = true; } } } else MUL(ans, 2); } if(S[K]) cout << ans << "\n"; else cout << 0 << "\n"; }