すべての組み合わせの合計を求めるので \(C_i\) は昇順にソートしても答えは変わらない. よってソートしておく.

まず, 操作の順序は \(C_i\) が小さいビットから順に行うのが最適である.

次に, あるビット \(i\) を操作したときに \(j\) 点得る \(S, T\) の組み合わせの数を考える.

\(i\) より左のビットは操作の際にはすでに操作を終えているので, なんでもいい. ビット \(i\) は当然異なっており, \(i\) より右のビットは \(j-1\) 個異なっている.

よって, \(S\) を決めたときにあり得る \(T\) の数は

\[2^{i-1} \times 1 \times \binom{N-i}{j-1}\]

である. よって, 総合計は,

\[2^N \times \sum_{i=1}^N C_i \times 2^{i-1} \times \left( \sum_{j=1}^{N-i+1} j \times \binom{N-i}{j-1} \right)\]

となる. ここで,

\[\sum_{j=1}^{N-i+1} j \times \binom{N-i}{j-1} = \sum_{j=0}^{N-i} (j+1) \times \binom{N-i}{j}\]

は \(f(x) = x(1+x)^{N-i}\) としたときの \(f^{\prime}(1)\) なので, 積の微分を用いて,

\[f^{\prime}(x) = (1+x)^{N-i} + (N-i)x(1+x)^{N-i-1}\]

となるので,

\[f^{\prime}(1) = 2^{N-i} + (N-i)2^{N-i-1}\]

となって \(O(\log N)\) で求めることができる.