ABC147 D問題 Xor Sum 4 - 輪郭をなぞるだけのブログ

排他的論理和 (XOR) は桁上がりのない加算 (ﾌﾞﾝｯﾌﾞﾝｯ ←素振り音)

atcoder.jp

問題

要素数 $N$ の数列 $A$ が与えられる。
$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} (A_{i}$ XOR $A_{j})$ を $10^9 + 7$ で割った余りを求めよ。

制約

$2 \leq N \leq 3 \times 10^{5}$
$0 \leq A_i \leq 2^{60}$
入力値はすべて整数である。

考察 → 実装

$O(N^2)$ で解けるなら、なんてことはない問題であるが、制約上厳しいものがある。
この問題を解く上では、次の気付きが重要である。

排他的論理和 (XOR) は桁上がりのない加算

大事なことなので二度言いました。
正しくは、二進表記における桁上がりのない加算である。
通常の加算には桁上がりがあるため、当然他の桁に影響を及ぼす。
ただし太字で書かれたことは、ある桁における演算が他の桁には影響を及ぼさないことを示している。

このことに気付けば、問題は半分くらい解けている。
まあ、気付くのに 40 分ほどかかったのだが…

XORが他の桁に影響を及ぼさないことは分かったが、和を取るときには当然桁上がりが発生するので、この性質は一見関係のないようにも思える。
実は、問題を解くには、もうワンステップ必要である。
まず、
$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} (A_{i}$ XOR $A_{j}) = \sum_{i=1}^{N(N-1)/2} B_{i}$
と書き換えてみる。
ただし、数列 $B$ は数列 $A$ の任意の二要素にXOR演算をした結果である。
数列 $B$ の要素 $B_{i}$ を $60$ 桁の二進表記で表すと、
$B_{i} = b_{59}b_{58} ... b_{0}$
となる。
$b_{d}$ は $B_{i}$ の二進表記における $d$ 桁目の bit を表す。( $d$ は 0-indexed としている。)
このとき、
$B_{i} = 2^{59} \times b_{59} + 2^{58} \times b_{58} + ... + 2^{0} \times b_{0}$
である。
$2$ のべき乗ごとに数列 $B$ の和を取っても結果は変わらないので、求める総和をそうやって求めることにする。
数列 $B$ の要素すべての二進表記が分かればいいが、数列 $B$ の要素数は、 $\begin{eqnarray*} && {}_N C _2 \end{eqnarray*}$ $=\frac{N(N-1)}{2}$ であり、素直にやっていては間に合わない。
ここで、計算量を削減するために、XORの性質が使える。
$d$ 桁目を見ているとき、数列 $B$ の要素の中で、 $d$ 桁目の bit が立っている個数がいくらかに興味がある。
これは、XORが他の桁に影響を及ぼさないことから、数列 $A$ の $d$ 桁目を調べれば求めることができる。

実際に行う操作としては、まず与えられた数列 $A$ の要素すべてに対して、二進表記で表したときの $d$ 桁目が $0,1$ である個数 $n_{0},n_{1}$ を数える。
表からも分かるように、 $(0,1)$ の組のみが $1$ になる。

^	1	0
1	0	1
0	1	0

求めたい個数は、 $n_{0} \times n_{1}$ で求まる。
これは、下図からも分かる通り、 $n_{0}$ 個の要素それぞれに $n_{1}$ 通りあるからである。
f:id:OutLine:20191217011327p:plain
数列 $B$ 中の $n_0 \times n_1$ 個は、 $d$ 桁目の bit が立っているものの個数である。
よって、数列 $B$ の $d$ 桁目の総和は、 $2^{d} \times n_{0} \times n_{1}$ で求まる。
各桁で求めたこの値を全て足し合わせれば、要求されたものを求めることができる。

計算量は、 $O(N \log (\max A_{i}))$ となる。
$\log (\max A_{i})$ は、二進表記の桁数を表す。(コードでは横着して 60 桁調べている。)

あと、個人的に躓いていたのだが、 $2^{d}$ を最初は単に (1 << d) と書いていた。
(これだと通らない。)
これだと、int型 (32bit) の整数を $d$ だけ左ビットシフトさせることとなり、右辺で計算しているときにオーバーフローしてしまうこともある。
右辺値は名前のない一時オブジェクトであり、整数リテラルは接尾辞がないと int などになるので、右辺で 32bit 整数として計算される。(本当かは分からない。)
なので、左辺に 64bit 整数であることを示したところで、望み通りの動作をしてくれない。
64bit 整数をビットシフトさせることを明示するために、ちゃんと (1ll << d) と書こう！
ll などの接尾辞はこういうためにあるんだね…(今さら)

整数リテラル - cppreference.com を見ると、接尾辞なしで long long int も許容されているが、うまくいかなかった気がする…
まあ、型を指定するのが無難だろう。

コード

#include <iostream>
#include <vector>
using namespace std;
 
const int mod = 1e+9 + 7;

int main(){
    int N;
    cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; ++i){
        cin >> A[i];
    }

    long long res = 0;
    for(int d = 0; d < 60; ++d){
        long long n0 = 0, n1 = 0;
        for(int i = 0; i < N; ++i){
            if((A[i] >> d) & 1) ++n1;   // d 桁目が 1
            else    ++n0;               // d 桁目が 0
        }
        long long tmp = (1ll << d) % mod;   // 2^d
        // B の要素 (xor 演算を施した数) で d 桁目が 1 である個数
        long long n = n0 * n1 % mod;
        // B の要素 (xor 演算を施した数) の d 桁目の総和 (= 2^d * n0 * n1)
        tmp = tmp * n % mod;
        res = (res + tmp) % mod;
    }
    cout << res << endl;
}