解説
期待値の線形性に関する問題です。
とします。
明らかにです。
定義より
であるため、の値を計算できれば期待値を計算することができます。以下このを求めることを考えましょう。
さて、を満たす自然数のペアに対して
と定義します。
この時対称性より、の値によらずの値は同じです。
これを用いると、期待値の線形性より
となります。
後は、を求めれば良いです。
この値は、 なる自然数に対して なる数列の要素が何個あるかを考えれば良いです。
のパターンに分けて考えると、
であることがシグマ計算を用いてで求まります。
以上より求める期待値の値は
です。
時間計算量はです。