長さ の数列 が与えられる。 から までの各整数はちょうど 2 回ずつ現れる。
要素を削除する順序を、すべての 通りから一様ランダムに選ぶ。この順序で元の要素を 1 つずつ削除し、残っている要素の相対的な順序は保たれる。
整数 の 2 つの要素が、削除を始める前または削除の途中で一度でも隣接した場合、 点を得る。各整数について得点するのは高々 1 回である。最終得点を とするとき、 の期待値を求めよ。
期待値を既約分数 と表したとき、 を で割った余りを出力せよ。 は を法とする の乗法逆元である。
入力は次の形式で与えられる。
の期待値を を法として出力せよ。
削除を始める前から 2 つの が隣接しているので、必ず 点を得る。したがって 、 である。
最初に中央の 2 要素のどちらかを削除すると、その後の削除順にかかわらず、ちょうど 1 種類の整数で得点する。最初に端の要素を削除した場合は、残った 3 要素の中央を 2 番目に削除したときだけ得点する。
よって の確率は で、それ以外は である。したがって であり、指定された法で表すと となる。
2 つの は最初から隣接しているので、必ず 点を得る。2 つの も隣接するには、両方の がどちらの よりも先に削除される必要があり、その確率は である。
よって の確率は 、 の確率は であり、 となる。指定された法で表すと である。
