#AT10. Sushi

Sushi

[J] Sushi(dp_j)

来源: AtCoder Educational DP Contest - Problem J 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 个盘子,编号 1,2,…,N1, 2, \ldots, N。初始时,第 ii 个盘子上盛有 aia_i(1≤ai≤31 \le a_i \le 3)个寿司。

太郎会重复下面的操作,直到所有寿司都被吃掉:

  • 抛一枚均匀的、取值为 1,2,…,N1, 2, \ldots, N 的骰子,设结果为 ii。若第 ii 个盘子上还有寿司,则吃掉其中一个;否则什么也不做。

求所有寿司被吃掉之前操作次数的期望值。

输入格式

输入由标准输入按以下格式给出:

N
a_1 a_2 \ldots a_N

输出格式

输出操作次数的期望值。答案与标准答案的相对误差不超过 10−910^{-9} 即判为正确。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤3001 \le N \le 300
  • 1≤ai≤31 \le a_i \le 3

样例 1

输入:

3
1 1 1

输出:

5.5

样例 2

输入:

1
3

输出:

3

样例 3

输入:

2
1 2

输出:

4.5

样例 4

输入:

10
1 3 2 3 3 2 3 2 1 3

输出:

54.48064457488221

注: 本题答案(期望次数)为实数,采用 Special Judge 按官方误差标准判题:相对误差不超过 10−910^{-9} 即判为正确。