問題概要
$n$ 項からなる正整数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる．次の値を求めよ：
\begin{equation*}
\sum_{ i = 1 }^{ n - 1 }\sum_{ j = i + 1 }^{ n }
( A_i \oplus A_{ i + 1 } \oplus \dots \oplus A_j )
\end{equation*}
ここで，二項演算 $\oplus$ は整数同士の bitwise xor を表す．
制約
- $2 \leq n \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^8$
解法
$\Omega( n^2 )$ 時間かけると TLE するので，愚直に計算することはできません．何か工夫した方法を考える必要があります．
与式において括弧の中身が bitwise xor であることから，総和への寄与をビット毎に独立に計算してから足しても同じ結果が得られます．下から $b$ ビット目 ($0$-based) に着目し，$b$ ビット目を取り出して得られる列を $B$ とします．正確には，$B$ は $n$ 項からなる列で
\begin{equation*}
B_i = \begin{cases}
0 & \text{($A_i$ の $b$ ビット目が $1$)} \\
1 & \text{(otherwise)}
\end{cases}
\end{equation*}
を満たすものです．$B$ の連続する部分列を表す記法として，次を導入します：
\begin{equation*}
B[ i, j ] := \langle B_i, B_{ i + 1 }, \dots, B_j \rangle
\end{equation*}
$i, j$ ($i < j$) を固定したときの $B[ i, j ]$ の答えへの寄与を考えます．xor をとることから足される値は $0$ か $1$ のいずれかであり，これは $B[ i, j ]$ に含まれる $1$ の個数の偶奇によって決まります．$\sum B[ i, j ]$ の偶奇であるとも言えます．よって，
\begin{equation*}
t = | \{ ( i, j ) \mid i, j \in \{ 1, 2, \dots, n \}, i < j, \sum B[ i, j ] \bmod 2 = 1 \} |
\end{equation*}
とすれば，$2^b$ が $t$ 回足されることが分かります．
以上から問題は，$n$ 項からなる $0, 1$ 列に対し，総和が奇数となる長さ $2$ 以上の連続部分列の個数を求める問題に帰着されます．部分列の総和の奇遇を愚直に計算するとどうにもならなそうなので，よりよい方法を考えます．とはいえ，「連続部分列の総和」といえば「累積和」が思い付きます．$B$ に対する累積和を $P$ とします：
\begin{equation*}
P_i = \begin{cases}
0 & \text{(i = 1)} \\
P_{ i - 1 } + B_{ i - 1 } & \text{(otherwise)}
\end{cases}
\end{equation*}
このとき実際，
\begin{equation*}
\sum B[ i, j ] = P_{ j + 1 } - P_i
\end{equation*}
となり，計算しやすくなります．ここで奇遇性に着目すると，$P_i, P_{ j + 1 }$ が奇数同士 or 偶数同士のとき総和が偶数となり，そうでないとき奇数となります．従って，$P_i$ が偶数（resp. 奇数）となる $i$ の個数を $k$ とすれば，総和が偶数（resp. 奇数）となる部分列の個数は二項係数 $\binom k 2$ と簡単に求まるので，部分列の取り方の総数から条件を満たさない部分列の個数を引くことで答えが求まりそうです．長さが $1$ で総和が $1$ な列も条件を満たさないことに注意します．
$P_i$ が偶数となる $i$ の個数を $c_i$, 奇数となる $i$ の個数を $c_1$ とすれば，各部分列の個数は，
- すべての部分列 : $\binom { n + 1 } 2 = \frac { ( n + 1 ) n } 2$ 個
- 総和が偶数となる部分列 : $\binom { c_0 } 2 + \binom { c_1 } 2 = \frac { c_0 ( c_0 - 1 ) } 2 + \frac { c_1 ( c_1 - 1 ) } 2$ 個
- 長さ $1$ で総和が $1$ である部分列 : $\sum B$ 個
となり，それぞれの値を計算して足し引きすることで，上述の $t$ が求まり，総和への寄与は $t 2^b$ であると分かります．あとは各 $b$ について同様のことをして総和をとれば答えが求まります．
計算量について述べます．まず $b$ として試すべき値は $\Theta( \log \max A )$ 個あります．そして各 $b$ について $b$ ビット目を抜き出す処理・累積和をとる処理・$0, 1$ の個数を数える処理にそれぞれ $\Theta( n )$ 時間かかります．その他の算数部分の計算量は無視できます．よって全体では $\Theta( n \log \max A)$ 時間となります．
コード
int main() { IN( int, N ); VI A( N ); cin >> A; LL res = 0; REP( b, 30 ) { VI B; transform( ALL( A ), BI( B ), [&]( const int a ){ return !!( a & 1 << b ); } ); VI psum( 1 ); partial_sum( ALL( B ), BI( psum ) ); LL zeros = 0, ones = 0; for_each( ALL( psum ), [&]( const int s ){ ++( s % 2 ? ones : zeros ); } ); const LL t = LL( N ) * ( N + 1 ) / 2 - zeros * ( zeros - 1 ) / 2 - ones * ( ones - 1 ) / 2 - accumulate( ALL( B ), 0 ); res += ( 1 << b ) * t; } cout << res << endl; return 0; }
