同じ値の要素の間にも適当に順序を定めます。\(A\) をソートすると、 \(A_i \times A_j\) \(\left(i < j\right)\) が答えに足し込まれる回数は \(2^{j-i-1}\)回ですから、この問題の答えは以下のように書けます。

\[ \sum_{i = 1}^N \sum_{j = i + 1}^N A_i \times A_j \times 2^{j-i-1} + \sum_{i = 1}^N A_i \times A_i \]

ここで、

\[ \sum_{i = 1}^N \sum_{j = i + 1}^N A_i \times A_j \times 2^{j-i-1} \]

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

であり、

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

ですから、(1) は \(i = N\) から降順に \(O\left(N\right)\) の時間計算量で計算出来ます。以上より、この問題は \(O\left(N\log N\right)\) の時間計算量で解けました。