CSAcademy - Xor Closure

問題概要

N 項からなる数列 {a_n} が与えられる.この数列にいくつか数を追加して,以下の性質を満たすようにする.

  • 相異なる任意の i, j に対して,a_i XOR a_j もまた数列 {a_n} に含まれる

このとき,{a_n} にいくつ数を追加すれば上記の性質を満たすようにできるか?

・制約
1 <= N <= 10^5
{a_n} の要素は相異なる.

解法

線形空間の定義そのままであることに気づければ勝ち.
つまり,この問題は,与えられた01ベクトル列の基底(というか次元)を求めてね,という問題に帰着できる.
次元を K とすると,答えは 2^K - N となる.

もうちょっと丁寧に書くと(とはいってもほとんど同じだけど),
{a_n} を 01上の線形(部分)空間にすることが目標.
二元体のベクトルが XOR と AND で線形空間をなすのは有名事実である.
部分空間 W の定義として,
任意の x, y ∈ W にたいして x + y ∈ W である
がある.これは問題文と同じ.
基底を e1, e2, ..., eK とすると,W の任意の元は
x = (c1 AND e1) XOR ... XOR (cK AND eK)
と表せるので,この線形空間の要素数は係数の割り当て方で 2^K 通り.
もともと N 個あるわけだから,2^K - N が答え.

ソースコード

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

using ull = unsigned long long;

// 直交するように基底を選んでいく
void binary_basis_insert(vector<ull>& w, ull a) {
    for(auto v : w) {
        if(v & (-v) & a) {
            a ^= v;
        }
    }
    if(a == 0) { // すでに生成可能
        return;
    }
    for(auto& v : w) {
        if(a & (-a) & v) {
            v ^= a;
        }
    }
    w.push_back(a);
}

vector<ull> binary_basis(vector<ull> const& w) {
    vector<ull> res;
    for(auto v : w) {
        binary_basis_insert(res, v);
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<ull> a(N);
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    auto basis = binary_basis(a);
    cout << (1ULL << basis.size()) - N << endl;
}

感想

http://codeforces.com/contest/587/problem/E
Codeforcesでほとんど同じ問題がある.Codeforcesのほうが難しい.