【Python】AtCoder Beginner Contest147 問題D

スポンサーリンク
AtCoder
スポンサーリンク

AtCoder Beginner Contest147問題D(Xor Sum4)の解法についてまとめました。

問題はこちらです。

N 個の整数があり、i番目の整数は Ai です。 \[ \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}(A_i XOR A_j) \]

を109+7で割った余りを求めてください。

排他的論理和XORでは、両方のビットが異なるとき1、同じとき0になります。

したがって、入力として1,2,3が与えられた時、以下のようなビット演算をすることになります。

この計算を見ると、それぞれのビットごとに0 XOR 1の演算を何回行ったかを数えれば良いことが分かります。

各ビットごとの0 XOR 1の回数は、(1の個数)×(0の個数)で求めることができます。

コードはこちらです。

タイトルとURLをコピーしました