\(V := (\mathbb{F}_{2}\) における \(N\) 次元ベクトル空間) の基底を求める問題. コストの小さいほうから貪欲に選んでいく.
コストを無視すれば,吐き出し法で基底は求まる. \(b\) を 1次独立な vector の集合として,\(V\) を span できるまで vector を追加する. 今調べている vector \(v\) が \(Span(b)\) に含まれていれば何もしない, そうでなければ \(v\) を \(b\) に追加する.
コストが有る場合も,コストが小さい方から vector を貪欲に選べばよい.
実装
\(b\) の中は順番がめちゃくちゃでも正しく求まるが, \(b_{i}\) を \(i\) 番目の component が non zero になる vector として記録すると楽.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
ll n2 = 1ll << n;
rep1(i,n2-1){
cin >> p[i].first;
p[i].second = i;
}
sort(all(p));
vll b(n);
ll ans = 0;
for(auto [c,i]: p) if(i){
rep(k,n) if(b[k]){
assert(b[k] >> k & 1);
if(i >> k & 1){
i ^= b[k];
}
}
if(i == 0) continue;
rep(k,n) if(i >> k & 1){
b[k] = i;
ans += c;
break;
}
}
rep(k,n) assert(b[k]!=0);
cout << ans << endl;
return 0;
}