あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC147 D - Xor Sum 4

競プロ数え上げ

問題原文

問題要旨

$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}A_i XOR A_j$ を $10^{9} + 7$ で割ったあまりを求めよ。

$2 \leq N \leq 3 × 10^{5}$
$0 \leq A_i \leq 2^{60}$

解法

XORは桁ごとに見るといいって言ってた。（というか制約の書き方ry）どちらかのbitが立っているときにのみ、XORでbitは立つので、「与式においてあるbitが何回数えられるか？」は「（あるbitが立っているものの数）× （あるbitが立っていないものの数）」で計算できる。

実装

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

D = defaultdict(int)
for a in A:
    for i in range(61):
        D[1 << i] += bool(a & (1 << i))

ans = 0
for key, value in D.items():
    ans += key * (value * (N - value))
    ans %= MOD

print(ans % MOD)

感想

たぶん　ANDでもORでも似たように答えが出せる。
大きな数を使った掛け算は重いので、ちょいちょいbitを取る or そうした数を使う計算を最小限にするように心がけたい。