#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e6+5;
double f[305][305][305];
int a[5],n; 
int main(int argc,char const *argv[]){
	scanf("%d",&n);
	for(int i=1,x;i<=n;++i){
		scanf("%d",&x);
		a[x]++;
	}	
	for(int k=0;k<=n;++k){
		for(int j=0;j<=n;++j){
			for(int i=0;i<=n;++i){
				if(i||j||k){
					if(i)f[i][j][k]+=f[i-1][j][k]*i/(i+j+k);
        			if(j)f[i][j][k]+=f[i+1][j-1][k]*j/(i+j+k);
    	    		if(k)f[i][j][k]+=f[i][j+1][k-1]*k/(i+j+k);
	        		f[i][j][k]+=(double)n/(i+j+k);
         		}
			}
		}
	}
	printf("%.15lf\n",f[a[1]][a[2]][a[3]]);
	return 0;
}

暴力dp

首先我们考虑最暴力的做法，用 $dp[a_1][a_2]...[a_n]$ 表示第 $i$ 盘还剩 $a_i$ 个寿司的期望次数。那么枚举随机到的数i就可以得到方程：

$dp[a_1][a_2]...[a_n] = 1 + \sum\limits_{i=1}^n \frac{1}{n} dp[a_1][a_2]...[\max(a_i - 1, 0)]...[a_n]$

合并状态

（注意该方程并不能构成转移方程，因为当第i盘已经为空的时候，状态不变）我们现在考虑合并等价状态（题外话：动态规划优化的初等方法无非就那么几种，合并状态就是最重要的思想之一）。

注意到由于随机数是均匀选取的，那么盘子的位置是无关紧要的，而只有剩余数量有影响。于是相同数值的不同排列的期望次数必然是相同的。例如 $dp[1][2][3] = dp[3][2][1]$。

所以只需要考虑每种数值出现的次数。因为 $a_i \leq 3$，所以至多有四种不同数值：0,1,2,3。我们重新定义状态 $dp[a][b][c][d]$ 表示当前还剩下 $a/b/c/d$ 盘有0/1/2/3个寿司。

有了状态，我们通过枚举当前随机到的盘子里还剩几只寿司得到如下方程：

$dp[a][b][c][d] = 1 + \frac{a}{n} dp[a][b][c][d] + \frac{b}{n} dp[a+1][b-1][c][d] + \frac{c}{n} dp[a][b+1][c-1][d] + \frac{d}{n} dp[a][b][c+1][d-1]$

移项整理得到转移方程：

$dp[a][b][c][d] = \frac{n}{b + c + d} + \frac{b}{b + c + d} dp[a+1][b-1][c][d] + \frac{c}{b + c + d} dp[a][b+1][c-1][d] + \frac{d}{b + c + d} dp[a][b][c+1][d-1]$

消除无用状态

但由于 $n \leq 300$，总状态数高达 $300^4 \approx 8 \times 10^9$ 无法通过。我们需要进一步优化。

注意到任意时刻下，$a + b + c + d$ 的值都应该等于 $n$：因为不管进行多少次操作，盘子总数总是 $n$ 。所以其实只需要知道 $b, c, d$ 就可以反推出 $a$ 的值：$a = n - (b + c + d)$ 。那么现在只保留后面三维，得到转移方程：

$dp[b][c][d] = \frac{n}{b + c + d} + \frac{b}{b + c + d} dp[b-1][c][d] + \frac{c}{b + c + d} dp[b+1][c-1][d] + \frac{d}{b + c + d} dp[b][c+1][d-1]$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e6+5;
double f[305][305][305];
int a[5],n; 
int main(int argc,char const *argv[]){
	scanf("%d",&n);
	for(int i=1,x;i<=n;++i){
		scanf("%d",&x);
		a[x]++;
	}	
	for(int k=0;k<=n;++k){
		for(int j=0;j<=n;++j){
			for(int i=0;i<=n;++i){
				if(i||j||k){
					if(i)f[i][j][k]+=f[i-1][j][k]*i/(i+j+k);
        			if(j)f[i][j][k]+=f[i+1][j-1][k]*j/(i+j+k);
    	    		if(k)f[i][j][k]+=f[i][j+1][k-1]*k/(i+j+k);
	        		f[i][j][k]+=(double)n/(i+j+k);
         		}
			}
		}
	}
	printf("%.15lf\n",f[a[1]][a[2]][a[3]]);
	return 0;
}

暴力dp
首先我们考虑最暴力的做法，用 $dp[a_1][a_2]⋅⋅⋅[a_n]$ 表示第 $i$ 盘还剩 $a_i$ 个寿司的期望次数。那么枚举随机到的数i就可以得到方程：
$dp[a_1][a_2]⋅⋅⋅[a_n]=1+\sum\limits_{i=1}^n \frac 1 n dp[a_1][a 2]⋅⋅⋅[max(a_i−1,0)]⋅⋅⋅[a_n]$

合并状态

（注意该方程并不能构成转移方程，因为当第i盘已经为空的时候，状态不变）我们现在考虑合并等价状态（题外话：动态规划优化的初等方法无非就那么几种，合并状态就是最重要的思想之一）。

注意到由于随机数是均匀选取的，那么盘子的位置是无关紧要的，而只有剩 余数量有影响。于是相同数值的不同排列的期望次数必然是相同的。例如 $dp[1][2][3]=dp[3][2][1]$。

所以只需要考虑每种数值出现的次数。因为 $a_i≤3$，所以至多有四种不同数值：0,1,2,3。我们重新定义状态dp[a][ b ][c][d]表示当前还剩下 a/b/c/d盘有0/1/2/3个寿司。

有了状态，我们通过枚举当前随机到的盘子里还剩几只寿司得到如下方程：

$dp[a][ b ][c][d]=1+\frac a n dp[a][ b ][c][d]+ \frac b n dp[a+1][b−1][c][d] + \frac c n dp[a][b+1][c−1][d]+ \frac d n dp[a][ b ][c+1][d−1]$

移项整理得到转移方程：

$dp[a][ b ][c][d]= \frac n {b+c+d} + \frac b {b+c+d} dp[a+1][b−1][c][d] + \frac c {b+c+d} dp[a][b+1][c−1][d]+ \frac d {b+c+d} dp[a][ b ][c+1][d−1] $

消除无用状态
但由于 $n≤300$，总状态数高达 $300^4≈8×10^9$ 无法通过。我们需要进一步优化。

注意到任意时刻下，$a+b+c+d$ 的值都应该等于 $n$ ：因为不管进行多少次操作，盘子总数总是 $n$ 。所以其实只需要知道 $b,c,d$ 就可以反推出 $a$ 的值：$a=n−(b+c+d)$ 。那么现在只保留后面三维，得到转移方程：

$dp[ b ][c][d]= \frac n {b+c+d} + \frac b {b+c+d} dp[b−1][c][d]+ 
\frac c {b+c+d} dp[b+1][c−1][d]+ \frac d {b+c+d} dp[ b ][c+1][d−1]$