推式子题。
设 $dp_{a,b,c,\dots}$ 表示每一个位置的寿司数量。由于 $n \leq 300$，直接寄了。
考虑合并相同信息，设 $dp_{i,j,k,l}$ 表示有 $i$ 个 $0$，$j$ 个 $1$，$k$ 个 $2$，$l$ 个 $3$。
然后空间仍然爆炸，由于总数 $n$ 不变，所以直接设 $dp_{i,j,k}$ 表示有 $i$ 个 $1$，$j$ 个 $2$，$k$ 个 $3$。

选择 $0$：$\frac{n-i-j-k}{n} (dp_{i,j,k}+1)$。
选择 $1$：$\frac{i}{n} (dp_{i-1,j,k}+1)$。
选择 $2$：$\frac{j}{n} (dp_{i+1,j-1,k}+1)$。
选择 $3$：$\frac{k}{n} (dp_{i,j+1,k-1}+1)$。

合并起来得到

$$dp_{i,j,k}=\frac{(n-i-j-k) \times (dp_{i,j,k}+1) + i \times (dp_{i-1,j,k}+1) + j \times (dp_{i+1,j-1,k}+1) + k \times (dp_{i,j+1,k-1}+1)}{n}$$

怎么计算 $dp_{i,j,k}$ 的式子包含它本身？
套用类似于 这题 的思路，通过移项求解。

$$dp_{i,j,k}=\frac{(n-i-j-k) \times dp_{i,j,k} + i \times dp_{i-1,j,k} + j \times dp_{i+1,j-1,k} + k \times dp_{i,j+1,k-1} + n}{n}$$
$$n \times dp_{i,j,k} - (n-i-j-k) \times dp_{i,j,k} = i \times dp_{i-1,j,k} + j \times dp_{i+1,j-1,k} + k \times dp_{i,j+1,k-1} + n$$
$$(i+j+k) \times dp_{i,j,k} = i \times dp_{i-1,j,k} + j \times dp_{i+1,j-1,k} + k \times dp_{i,j+1,k-1} + n$$
$$dp_{i,j,k} = \frac{i \times dp_{i-1,j,k} + j \times dp_{i+1,j-1,k} + k \times dp_{i,j+1,k-1} + n}{i+j+k}$$

转移即可，由于要保证无后效性，要根据 $k,j,i$ 的顺序枚举转移。

#include <bits/stdc++.h>
using namespace std;
const int N = 315;

int n, a[N], c[4];
double dp[N][N][N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), c[a[i]]++;
    dp[0][0][0] = 0;
    for (int k = 0; k <= n; k++)
        for (int j = 0; j <= n; j++)
            for (int i = 0; i <= n; i++) {
                if (i == 0 && j == 0 && k == 0) continue;
                double res = 0, p = i + j + k;
                if (i) res += i * 1.0 * dp[i - 1][j][k] / p;
                if (j) res += j * 1.0 * dp[i + 1][j - 1][k] / p;
                if (k) res += k * 1.0 * dp[i][j + 1][k - 1] / p;
                res += n * 1.0 / p;
                dp[i][j][k] = res;
            }
    printf("%.9lf\n", dp[c[1]][c[2]][c[3]]);
    return 0;
}