F - Xor Sum 3
[Q] https://atcoder.jp/contests/abc141/tasks/abc141_f
・基底を取り出すところまで解説どおり。
Nを60まで減らせる。
https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-09-14abc-141#toc5
1. 引数をちょっと下処理。
全部の論理和 all をとったときに、1が立っているbitはどうred/blueにふりわけても、1回だけ1が立つのがわかるので、あらかじめ解答に含める。また、A[N]から~allを除いておく。(※これをしないと、解答が小さくなってしまうバグ）
2. 基底を抽出し降順にする。これは allのbit が0だった要素なので、うまくred/blueに振り分けられれば2倍おいしい要素。
3. 2.は上位bitから全部xorするのが最善。
Q. 1が立ってるbitの下処理？
入力例2
4
23 36 66 65
bit
23 = 0010111
36 = 0100100
66 = 1000010
65 = 1000001
------------
xor= 0110000
1が立っている箇所はred/blueにどう振り分けても1回立つので、ansにストック。
0110000 を逆転させた
1001111 との論理積をとって、A[N]をきれいにする。
A. 下処理
7 = 0000111
4 = 0000100
66 = 1000010
65 = 1000001
として扱う。Q. 基底の抽出？
A. 解答例に準拠。掃き出し法なる名称があるよう。
59bit目から0bit目まで探索する。
上位bitが立っているものを探す。
最初に見つかったものを基底にし、以降見つかったものはxorして打ち消す。
最終的に、項数Nは上位bitの立っている項数(最大60個)まで減らせる。それ以外は全部0になる。
実装
int main(){
cincout();
ll N;
cin >> N;
vector<ll> A(N);
ll all = 0;
rep(i, N){
cin >> A[i];
all ^= A[i];
}
ll ans = all; // allが立ってるなら、red/blueどちらかに1回含まれるので加算しておく
rep(i, N) A[i] &= ~all; // 奇数bitは省いておく。これをしないと解答が少なく出る…。
ll seen=0;
// 掃き出し法
for(ll i=59; i>=0; --i){
ll base = -1; // 1LL<<iが存在するid
for(ll j=seen; j<N; ++j){
if ((A[j]>>i) & 1){
if (base>-1) A[j]=A[j]^A[base];
else base = j;
}
}
if (base>-1){
rep(j, seen){
if ((A[j]>>i) & 1){
A[j]=A[j]^A[base];
}
}
swap(A[base], A[seen]); // sort
++seen;
}
}
ll x=0;
rep(i, N){
if (A[i]==0) break;
x ^= A[i];
}
cout << ans + x*2 << endl;
}