Codeforces Good Bye 2020 E. Apollo versus Pan - 人間だけど競プロやる

Good Bye 2020 E. Apollo versus Pan

まず、

シグマをみたら式変形
ビット演算は桁ごとに見る

のが基本なのでやってみる

$\displaystyle{\sum^{N}_{i} \sum^{N}_{j} \sum^{N}_{k} {(x_i \& x_j) \times (x_j | x_k )}}$

$(x_i \& x_j)$ は $k$ に依存しないのでシグマの外に出す

$\displaystyle{\sum^{N}_{i} \sum^{N}_{j} {(x_i \& x_j)} \times \sum^{N}_{k} { (x_j | x_k )}}$

$(x_i \& x_j)$ と $(x_j | x_k)$ の両者が $j$ に依存するので、シグマの順番を入れ替える

$\displaystyle{\sum^{N}_{j} \sum^{N}_{i} {(x_i \& x_j)} \times \sum^{N}_{k} { (x_j | x_k )}}$

$\displaystyle{\sum^{N}_{j} \biggl( \sum^{N}_{i} {(x_i \& x_j)} \times \sum^{N}_{k} { (x_j | x_k )} \biggr)}$

これはプログラムで書くと、

let mut ans = 0;
for i in 0..N {
    let mut x = 0;
    let mut y = 0;
    for j in 0..N {
        x += a[i] & a[j];
        y += a[i] | a[j];
    }
    ans += x * y;
}

となる
このままでは $O(N^2)$ となり間に合わないので、forの中のビット演算を桁ごとにみることで計算量を減らしたい。
この式（プログラム）を解釈すると、 $a_i$ を順番にみていって、各 $a_i$ にたいして、 $a_i$ から $a_N$ までとANDとORをとって足したものを掛け合わせたものを、足していっている。
つまり、 $a_i$ をみたときに、 $a_i$ から $a_N$ までとAND（OR)をとった和が高速に求まれば良い。

これはよくある設定で、
2進数で各桁でみていってとき、 $a_i$ のd桁目が「1」なら、 $a_i$ から $a_N$ での各数のd桁目が「1」なら「AND」をとった結果は「1」となり、「0」なら「AND」をとった結果は「0」となる。
同様に $a_i$ のd桁目が「1」なら、 $a_i$ から $a_N$ での各数のd桁目が「1」「0」どちらであれ「OR」とった結果は1になる。 $a_i$ のd桁目が「0」なら、 $a_i$ から $a_N$ での各数のd桁目が「1」なら「1」、「0」なら「0」となる。
d桁目が「1」になる場合がいくつあるのかがわかれば、それらの和は $2^d \times$ いくあるかで求めることが出来る。 (2進数でd桁目は $2^k$ )
つまり、 $a_i$ から $a_N$ までの各数にたいして、d桁目が「1」がいくつあるかの分布がわかれば高速に求めることが出来る。

modを自分で毎回とるとバグりがち＆「1 << d」とかを32bitで処理しないように注意。
この方法でAC。