解説

期待値の線形性に関する問題です。

$(Num,Den) = (すべてのパターンの数列に対するコストの総和,ありうるすべてのパターンの個数)$

とします。

明らかに$Den = K^N$です。

定義より

$E = \frac{Num}{Den}$

であるため、$Num$の値を計算できれば期待値$E$を計算することができます。以下この$Num$を求めることを考えましょう。

さて、$1 \le i < j \le N$を満たす自然数のペア$(i,j)$に対して

$P(i,j) := A[i],A[j]の二項間におけるNumへのコストへの寄与の総和$

と定義します。

この時対称性より、$(i,j)$の値によらず$P(i,j)$の値は同じです。

これを用いると、期待値の線形性より

$Num = \displaystyle \sum_{i< j}^{} P(i,j)$

$= \displaystyle \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} P(i,j)$

$= \frac{N(N-1)}{2} * P(1,2)$

となります。

後は、$P(1,2)$を求めれば良いです。

この値は、$1\le i \le K$ なる自然数$i$に対して $min(A[1],A[2]) = i$なる数列$A$の要素が何個あるかを考えれば良いです。

$(1) A[1] > A[2]$

$(2) A[1] < A[2]$

$(3) A[1] = A[2]$

の$3$パターンに分けて考えると、

$P(1,2) = K ^ {N - 2}(K^2(K + 1) - \frac{K(K + 1)(4K - 1)}{6})$

であることがシグマ計算を用いて$O(1)$で求まります。

以上より求める期待値の値は

$E = \frac{\frac{N(N-1)}{2} * K ^ {N - 2}(K^2(K + 1) - \frac{K(K + 1)(4K - 1)}{6})}{K^N}$

です。

時間計算量は$O(1)$です。