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のほうが難しい.