142AC - SoundHound (C): Ordinary Beauty

SoundHound-C (300 points)

問題

数列 $(a_1, a_2, \ldots , a_n)$ の美しさを以下で定義するとき, 各要素が $1$ 以上 $n$ 以下の整数である長さ $m$ の数列（ $n ^ m$ 通り存在）の美しさの平均を求める.
数列 $a_1, a_2, \ldots , a_n$ の美しさ $=$ 隣り合う $2$ 項の組であって, 差の絶対値が $d$ であるものの個数

$0 \leq d < n \leq 10^9$
$2 \leq m \leq 10^9$
入力は全て整数

方針

けんちょん先生（＠drken）の記事を読んだ方が早い.
$1$ 以上 $n$ 以下の整数 $a, b$ をランダムに選ぶとき, 確率変数 $X_{a, b}$ を
$X_{a, b} = \left\{ \begin{array}{ll} 1 & (|a - b| = d) \\ 0 & (otherwise) \end{array} \right.$
と定義すると,
$P(X_{a, b} = 1) = \left\{ \begin{array}{ll} \frac{2(n - d)}{n^2} & (d \neq 0) \\ \frac{n - d}{n^2} = \frac{1}{n} & (d = 0) \end{array} \right.$
となるので, 期待値の線形性から
$\begin{equation} \begin{split} E[ \sum_{i = 1}^{m - 1} X_{a_i, a_{i + 1}} ] &= \sum_{i = 1}^{m - 1} E[ X_{a_i, a_{i + 1}} ] \\ &= \left\{ \begin{array}{ll} \frac{2(m - 1)(n - d)}{n^2} & (d \neq 0) \\ \frac{(m - 1)}{n} & (d = 0) \end{array} \right. \end{split} \end{equation}$

# input
n, m, d = map(int, input().split())

ex = 2 * (n - d) / (n ** 2)

if d == 0:
    ans = ex * (m - 1) / 2
else:
    ans = ex * (m - 1)

print(ans)