解説


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

とします。

明らかにです。

定義より

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

さて、を満たす自然数のペアに対して

と定義します。

この時対称性より、の値によらずの値は同じです。

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

となります。

後は、を求めれば良いです。

この値は、 なる自然数に対して なる数列の要素が何個あるかを考えれば良いです。

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

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

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

です。

時間計算量はです。