⛳

ABC 147 | D - Xor Sum 4

2020/12/29に公開

競プロ

xor

bitごとに演算

tech

問題

解法

愚直にやると $O(N^2)$ でTLEしてしまう。

$N=3$ のときは以下のようになる。

入力例1のときを考えると以下である。

1ビット目に注目すると $XOR$ なので $A_i$ と $A_j$ のどちらかのビットが $1$ でどちらかのビットが $0$ であれば1ビット目が1になる。
ということは $A_i$ の中で1ビット目が $0$ の数と $1$ の数をかけあわせれば $A_i, A_j (i < j)$ の組み合わせで1ビット目が1になる組み合わせの数が求められる。
同様に各ビット組み合わせの数を数えて $i$ ビット目なら $2^{i -1}$ をかけて足し合わせれば答えとなる。

コード


#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

using mint = modint1000000007;

int main() {
  ll n;
  cin >> n;
  vector<int> bits(60);  // iビット目(0-indexed)までの1の個数を入れる
  for (int i = 0; i < n; i++) {
    ll a;
    cin >> a;
    for (int i = 0; i < 60; i++) {
      bits[i] += (a >> i & 1);
    }
  }
  mint ans = 0;
  for (int i = 0; i < bits.size(); i++) {
    ans += mint(2).pow(i) * (bits[i] * (n - bits[i]));
  }

  cout << ans.val() << endl;
}

ABC 147 | D - Xor Sum 4

問題

解法

コード

参考

Discussion