[AtCoder] ABC 147 D – Xor Sum 4

2019年12月17日

問題

方針

各ビットごとに着目

整数 \( A, B\) を \( 2 \) 進数表記で下位から \( i\) ビット目を \( a_i, \ b_i \) と表します。例えば、\( A = a_1a_2a_3 \) , \( B = b_1b_2b_3 \) としたとき、

\[ A \oplus B = a_1 \oplus b_1 + 2 \times a_2 \oplus b_2 + 2^2 \times a_3 \oplus b_3\]

と計算できます。ここで、整数 \( A_i \) の \( j \ (0 \leq j \leq 60) \) 番目のビットを \( a(i, j) \) として、次の計算を考えます。

\[
\begin{eqnarray}
\sum_{i = 2}^{N} A_1 \oplus A_i &=& \sum_{i = 1}^{N} \sum_{j=0}^{60} 2^{j} \times a(0, j) \oplus a(i, j)\\
&=& \sum_{j=0}^{60} 2^{j} \sum_{i = 1}^{N} a(0, j) \oplus a(i, j)
\end{eqnarray}
\]

上記の計算において、

\[ \sum_{i = 1}^{n} a(0, j) \oplus a(i, j)\]

は、\( N \) 個の整数において \( j \) 番目のビットが何個立っているかを知っていれば計算できるので、その累積和をあらかじめ計算しておきます。

コード