\(N!\) 通りの並べ方を一様ランダムに選ぶときのスコアの期待値を求め、最後に \(N!\) 倍すると考えることにします。

人 \(i,j\) の組がどれだけ期待値に寄与するか考えます。

\(N\) 人を一列に並べたときの人\(i,j\) の位置をそれぞれ \(C_i,C_j\) とすると、\(B_j-B_i=C_j-C_i\) のとき、かつ、そのときに限りスコアに \(S_{B_j-B_i}\) だけ寄与します。並べ方がそのような条件を満たす確率は、\(B_j-B_i< N\) のとき \(\displaystyle \frac{N-(B_j-B_i)}{N(N-1)}\)、そうでないとき \(0\) です。(組 \((C_i,C_j)\) は \(N(N-1)\) 通りの値を一様にとり、そのうち\(B_j-B_i=C_j-C_i\) となるものが \(N-(B_i-B_j)\) 通りある)

したがって、求める期待値は \(\sum_{i<j}S_{B_j-B_i}\frac{N-(B_j-B_i)}{N(N-1)}\) となります。

ここでこの確率は \(B_j-B_i\) のみに依存していることから、\(B_j-B_i\) の値ごとにまとめて計算することを考えます。つまり、\(1\leq i<j \leq N\) を満たす組 \((i,j)\) のうち、\(B_j-B_i=K\) となるものの個数を \(g(K)\) とすると、求める期待値は \(\sum_{k=1}^{N-1}g(k)S_k \frac{N-k}{N(N-1)}\) となります。

\(g\) はFFTを用いて \(O(N\log N)\) で求めることができるため、全体で \(O(N\log N)\) でこの問題が解けました。

実装例(C++)