[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;
}

https://atcoder.jp/contests/abc141/submissions/26045905