吃寿司期望(Sushi)

题目描述

$N$ 枚の皿があります。 皿には $1,\ 2,\ \ldots,\ N$ と番号が振られています。 最初、各 $i$ ($1\ \leq\ i\ \leq\ N$) について、皿 $i$ には $a_i$ ($1\ \leq\ a_i\ \leq\ 3)$ 個の寿司が置かれています。

すべての寿司が無くなるまで、太郎君は次の操作を繰り返し行います。

• $1,\ 2,\ \ldots,\ N$ の目が等確率で出るサイコロを振り、出目を $i$ とする。 皿 $i$ に寿司がある場合、皿 $i$ の寿司を $1$ 個食べる。 皿 $i$ に寿司が無い場合、何も行わない。

すべての寿司が無くなるまでの操作回数の期待値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

すべての寿司が無くなるまでの操作回数の期待値を出力せよ。 相対誤差が $10^{-9}$ 以下ならば正解となる。

样例输入 #1

3
1 1 1

样例输出 #1

5.5

样例输入 #2

1
3

样例输出 #2

3

样例输入 #3

2
1 2

样例输出 #3

4.5

样例输入 #4

10
1 3 2 3 3 2 3 2 1 3

样例输出 #4

54.48064457488221

数据范围

制約

• 入力はすべて整数である。
• $1\ \leq\ N\ \leq\ 300$
• $1\ \leq\ a_i\ \leq\ 3$

Sample Explanation 1

$1$ 個目の寿司を食べるまでの操作回数の期待値は $1$ です。 その後、$2$ 個目の寿司を食べるまでの操作回数の期待値は $1.5$ です。 その後、$3$ 個目の寿司を食べるまでの操作回数の期待値は $3$ です。 よって、全体の操作回数の期待値は $1\ +\ 1.5\ +\ 3\ =\ 5.5$ です。

Sample Explanation 2

例えば、3.00, 3.000000003, 2.999999997 などを出力しても正解となります。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接