独立って大切。(SoundHound Inc. Programming Contest 2018 -Masters Tournament-)

（注）これは競技プログラミングの問題解説記事です。

さて中学数学の復習をしよう。確率の話だ。

確率の中で最も重要な概念の一つに独立の概念がある。一方の事象が変化したとしても他方の事象に変化を与えない時、これらの事象は互いに独立であるという。

事象が互いに独立であると何が嬉しいことがあるのか。両事象が同時に起こる確率がそれぞれの事象が起こる確率の積に等しくなるのだ。積事象の確率を考える際に、独立だと各事象を観察すればいいので計算が楽になる。

ちゃんと表現すると以下の様になる。

「 $A$ と $B$ が独立である」 $\Leftrightarrow \ P(A \cap B) = P(A)P(B)$

さて、前置きはさておき、問題に入っていく。

問題

問題はこちら。

atcoder.jp

簡単に紹介する。

$1$ 以上 $N$ 以下の数からなる数列 $a$ がある。数列の長さが $M$ で、この数列の「美しさ」は以下で定義される。

$| \ a_{i+1} - a_i \ | = d$ を満たす様な $i$ の個数

数列は全部で $n^m$ 通り考えられるが、それぞれの数列で美しさを計算し、美しさの平均値を出力せよ。

入力：N, M, d

出力：数列 $a$ の美しさの平均値

まず具体例

まず素直に考えてみる。例えば、 $N=2, \ M=3, \ d=1$ の場合を考える。

数列 $a$	美しさ
{1, 1, 1}	0
{1, 1, 2}	1
{1, 2, 1}	2
{1, 2, 2}	1
{2, 1, 1}	1
{2, 1, 2}	2
{2, 2, 1}	1
{2, 2, 2}	0

よって平均値は(0 + 1 + 2 + 1 + 1 + 2 + 1 + 0) / 8 = 1。

考察

$0 \leqq N \leqq 10^9$ 、 $2 \leqq M \leqq 10^9$ なので全事象全てに対して美しさを計算することができない。ここで気づけるといいのが各区間同士が独立であるということだ。つまり前の区間の差の絶対値がdであることは現区間の差の絶対値がdであることに影響を与えることはなく、それぞれ別々に考えることができるということになる。

よって美しさは１区間の美しさが1になる確率を求めて（確率が美しさの期待値そのものとなる）、総区間数 $M-1$ をかければいい。

１区間の美しさが1になるのは、 $(a_i, a_{i+1}) = (1, d+1), (2, d+2), ... , (N-d, d), (N, N-d), ... , (d+1, 1)$ の $2N - 2d$ 通りである。 $d = 0$ の時だけ別に考える必要があり、この時は $(1, 1), \ (2, 2), ..., \ (N, N)$ の $N$ 通りである。