【ABC147】D - Xor Sum 4
解法
問題文通り実装してもO(N2)で間に合わない。
XOR演算を繰り返すため、ビットごとに考えたくなる。
そこで位ごとに、ビットが立っているかどうかをA[i]すべてで調べ、いくつビットが立っているかを計算することにする。
A[i] ≦ 260 なので、60の長さの配列を準備しておけば良い。
この配列をbit_cntと呼ぶことにする。
この計算ができたら、A[i]のjビット目が答えにどれだけ影響を与えるかを計算していく。
具体的には、
- A[i]のjビット目が立っている場合
- jビット目が立っていない要素が他にいくつあるかを考える
- N - bit_cnt[j]がそれに該当するが、既に見た要素も含まれているのでiを引いておく(重複して計算するのを回避するため)
- つまり、2j * (N - i - bit_cnt[j])を答えに加算する
- bit_cnt[j]を一つ減らす
- A[i]のjビット目が立っていない場合
- jビット目が立っている要素が他にいくつあるかを考える
- それは、bit_cnt[j]が該当する
- つまり、2j * bit_cnt[j] を答えに加算する
実装
modintを使うと実装が楽。
bit演算についてはこの記事がとても分かりやすい。
void solve(long long N, std::vector<long long> A){ vector<int> bit_cnt(60, 0); REP (i, N) { REP (j, 60) { // A[i]のjビット目が立っている場合 // bit_cnt[j]に加算 if (A[i] & (1LL << j)) bit_cnt[j]++; } } mint ans = 0; REP (i, N) { REP (j, 60) { mint n = (1LL << j); // A[i]のjビット目が立っている場合 if (A[i] & (1LL << j)) { ans += n * (N - i - bit_cnt[j]); bit_cnt[j]--; } else { ans += n * bit_cnt[j]; } } } cout << ans << endl; }```