permutation difference sum

並べ替えた後の数列 $B$ において $B_i=A_x,B_{i+1}=A_y$ となり、答えに $|A_x-A_y|$ が寄与する回数を主客転倒の考え方を用いて求めていきます。

• まず $x,y$ を $1 \le x,y \le N$ を満たすように選んで固定します。
• $i$ は $1 \le i \le N-1$ を満たすように自由に選べるので常に $N-1$ 通りあります。
• $A_x,A_y$ 以外の要素はどのように並んでいてもよいので $(N-2)!$ 通りあります。

以上より $\displaystyle (N-1)!\sum_{1 \le x,y \le N}|A_x-A_y|$ が答えになります。これを愚直に求めると $O(N^2)$ になるので間に合います。

なお、$A$ が昇順ソートされている場合は

$\displaystyle \sum_{1 \le x,y \le N}|A_x-A_y|=2\sum_{y =1}^{N}\sum_{x=1}^{y}(A_y-A_x)=2\sum_{y =1}^{N}(yA_y-\sum_{x=1}^{y}A_x)$

となります。よって $A$ をソートし $\displaystyle \sum_{x=1}^{y}A_x$ の部分を累積和で前計算してからこの式に従って求めると $O(N \log N)$ で解くことも可能です。