CODE THANKS FESTIVAL 2017,F: Limited Xor Subset

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