OMC095(E)

　すべての順列に対するスコアの総和 $S$ を求めればよい. これは $272$ 以下の正整数 $i,j$ に対して $|i-j|$ の寄与がそれぞれ $2\times256\times 270!$ 回であることに留意すれば, $$\begin{aligned} S&=\displaystyle 2\times256\times 270!\times\sum_{i=1}^{272}\sum_{j=1}^{i}(i-j)\\ &=256\times270!\times\sum_{i=1}^{272}(i^2-i)\\ &=\dfrac{1}{3}\times 256\times 273! \end{aligned}$$ 　以上より求める平均は $S/272!=256\times273/3=\textbf{23296}$ である.