2014 Yandex.Algorithm Elimination Stage, Round1 D - Splitting Money

問題文

問題概要

n 個の数列が与えられる．
各要素について，集合Aとして使うか，集合Bとして使うか，あるいは使わないかを選択できる．
最終的に，集合Aとして使った数字のXORと，集合Bとして使った数字のXORが等しくなるようにしたい．
そのような集合AとBは何通りあるか．ただし，同じ数字であっても，元の数列で違う位置にあるものであれば，それらは区別するものとする．

・制約
1 <= n <= 10^4
1 <= a_i <= 10^4

解法

まず，数字の値が小さいことに注目する．

また，集合AのXORと集合BのXORが等しいとは，そもそもどちらかの集合に含めるとしたすべての要素のXORが0であることと同値である．
そのように数字を選んだ場合，各要素をどちらに振り分けても，それぞれのXORの値は等しくなる．

以上の2つから，以下の dp で計算することができる．
dp[i][j] := i 番目の要素まで見て，どちらかの集合として使う要素の XOR の値が j となるような値の振り分け方

ある数字を集合として使う時，どちらの集合に入れるかで2通りあるので，遷移は
dp[i + 1][j ^ a[i]] += dp[i][j] * 2
となる．

計算量は O(n * a_i) ．

ソースコード

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

constexpr int mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> dp(1 << 14);
    dp[0] = 1;
    for(int i = 0; i < n; ++i) {
        auto nxt = dp;
        for(int j = 0; j < (int)dp.size(); ++j) {
            const int x = j ^ a[i];
            if(x < (int)nxt.size()) {
                (nxt[x] += (2 * dp[j]) % mod) %= mod;
            }
        }
        dp = move(nxt);
    }
    cout << dp[0] << endl;
}