Problem:
 Score : 100 points    Problem Statement There are N dishes, numbered 1, 2, \ldots, N .
Initially, for each i ( 1 \leq i \leq N ), Dish i has a_i ( 1 \leq a_i \leq 3 ) pieces of sushi on it.  Taro will perform the following operation repeatedly until all the pieces of sushi are eaten:   Roll a die that shows the numbers 1, 2, \ldots, N with equal probabilities, and let i be the outcome. If there are some pieces of sushi on Dish i , eat one of them; if there is none, do nothing.   Find the expected number of times the operation is performed before all the pieces of sushi are eaten.      Constraints  All values in input are integers.  1 \leq N \leq 300  1 \leq a_i \leq 3         Input Input is given from Standard Input in the following format:  N  a_1  a_2  \ldots  a_N       Output Print the expected number of times the operation is performed before all the pieces of sushi are eaten.
The output is considered correct when the relative difference is not greater than 10^{-9} .        Sample Input 1 3
1 1 1      Sample Output 1 5.5  The expected number of operations before the first piece of sushi is eaten, is 1 .
After that, the expected number of operations before the second sushi is eaten, is 1.5 .
After that, the expected number of operations before the third sushi is eaten, is 3 .
Thus, the expected total number of operations is 1 + 1.5 + 3 = 5.5 .       Sample Input 2 1
3      Sample Output 2 3  Outputs such as 3.00 , 3.000000003 and 2.999999997 will also be accepted.       Sample Input 3 2
1 2      Sample Output 3 4.5       Sample Input 4 10
1 3 2 3 3 2 3 2 1 3      Sample Output 4 54.48064457488221

Solution (Python):
n = int(input())

dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]


for i in range(n+1):
    for j in range(n-i+1):
        for k in range(n-i-j+1):
            ext = i + j + k
            if ext == 0:continue
            dp[i][j][k] = n/ext
            if i > 0:
                dp[i][j][k] += i/ext*dp[i-1][j+1][k]
            if j > 0:
                dp[i][j][k] += j/ext*dp[i][j-1][k+1]
            if k > 0:
                dp[i][j][k] += k/ext*dp[i][j][k-1]

a = list(map(int,input().split()))
q = [0,0,0,0]
for i in a:
    q[i] += 1

print(dp[q[3]][q[2]][q[1]])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0.] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1-k):
            for i in range(N+1-j-k):
                ijk = float(i + j + k)
                if ijk == 0:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0.] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1-k):
            for i in range(N+1-j-k):
                ijk = float(i + j + k)
                if ijk == 0:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))

ones , twos, threes = 0,0,0

for i in a:
  if i ==1:
    ones+=1
  elif i ==2:
    twos+=1
  else:
    threes+=1

max_ones = ones+twos+threes
max_twos = twos+threes
max_threes = threes

dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]

for k in range(max_threes+1):
  for j in range(max_twos+1-k):
    for i in range(max_ones+1-j-k):
      if i+j+k==0:
        continue
      else:
        dp[i][j][k] = n/(i+j+k)
        if i>0:
          dp[i][j][k] += (dp[i-1][j][k]*i)/(i+j+k)
        if j>0:
          dp[i][j][k] += (dp[i+1][j-1][k]*j)/(i+j+k)
        if k>0:
          dp[i][j][k] += (dp[i][j+1][k-1]*k)/(i+j+k)
          
          
print(dp[i][j][k])

Solution (Python):
N=int(input())
A=list(map(float,input().split()))
a,b,c=0,0,0
for i in range(N):
  if A[i]==1:
    a+=1
  elif A[i]==2:
    b+=1
c=N-a-b
i=1
dp=[[[0]*(N+2) for i in range(N+2)] for j in range(N+2)]
for k in range(c+1):
  for j in range(N-k-a+1):
    for i in range(N-k-j+1):
      if i==0 and j==0 and k==0:
        continue
      dp[k][j][i]=(dp[k][j][i-1]*i+dp[k][j-1][i+1]*j+dp[k-1][j+1][i]*k+N)/(i+j+k)
print(dp[c][b][a])

Solution (Python):
from collections import Counter
 
n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]  
 
for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])

Solution (Python):

import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = [[[0 for _ in range(n+1)] for __ in range(n+1)] for ___ in range(n+1)]

dp[n][n][n] = 0
divT = [1/i for i in range(1,n+1)]

for x in range(n,cnt[1]+cnt[2]-1,-1):
    for y in range(x,cnt[2]-1,-1):
        for z in range(y,-1,-1):
            delta = n*divT[n-z-1]
            if x != n:
                dp[x][y][z] += (dp[x+1][y][z] + delta) * (n-x)
            if y != x:
                dp[x][y][z] += (dp[x][y+1][z] + delta) * (x-y)
            if z != y:
                dp[x][y][z] += (dp[x][y][z+1] + delta)* (y-z)
            dp[x][y][z] *=divT[n-z-1]

print(dp[cnt[1]+cnt[2]][cnt[2]][0])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    N = int(input())
    a = tuple(map(int, input().split()))
    c1 = a.count(1) 
    c2 = a.count(2) 
    c3 = a.count(3) 

    dp = [[[0.0]*(N+1) for _ in range(N+1)] for __ in range(N+1)]
    for i in range(c3+1):
        for j in range(c2+c3-i+1):
            for k in range(N-i-j+1):
                if i == j == k == 0:
                    continue
                tmp = N
                if k != 0:
                    tmp += k*dp[k-1][j][i]
                if j != 0:
                    tmp += j*dp[k+1][j-1][i]
                if i != 0:
                    tmp += i*dp[k][j+1][i-1]
                dp[k][j][i] = tmp/(i+j+k)

    print(dp[c1][c2][c3])

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))


dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

one = A.count(1)
two = A.count(2)
three = A.count(3)


for k in range(three + 1):
    
    for j in range(two + three - k + 1):
        
        
        
        for i in range(one + two + three - k - j + 1):
            
            
            
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = 1.0*n
            if i > 0:
                tmp += i * dp[i - 1][j][k]
            if j > 0:
                tmp += j * dp[i + 1][j - 1][k]
            if k > 0:
                tmp += k * dp[i][j + 1][k - 1]
            
            dp[i][j][k] = tmp / (i + j + k)

print(dp[one][two][three])

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=1
dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]
for k in range(c+1):
  for j in range(n-k-a+1):
    for i in range(n-k-j+1):
      if i==0 and j==0 and k==0:
        continue
      dp[k][j][i]=(dp[k][j][i-1]*i+dp[k][j-1][i+1]*j+dp[k-1][j+1][i]*k+n)/(i+j+k)
print(dp[c][b][a])

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K



dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):
    for m in range(min(n,M)+1):
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
a = A.count(1)
b = A.count(2)
c = A.count(3)
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
 


for k in range(c + 1):
    for j in range(b + c + 1 - k): 
        for i in range(a + b + c + 1 - k - j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = N * 1.0
            if i > 0:
                tmp += i * dp[i-1][j][k]
            if j > 0:
                tmp += j * dp[i+1][j-1][k]
            if k > 0:
                tmp += k * dp[i][j+1][k-1]
            dp[i][j][k] = tmp / (i + j + k)
print(dp[i][j][k])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
a = A.count(1)
b = A.count(2)
c = A.count(3)
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]



for k in range(c + 1):
    for j in range(b + c + 1 - k): 
        for i in range(a + b + c + 1 - k - j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = N * 1.0
            if i > 0:
                tmp += i * dp[i-1][j][k]
            if j > 0:
                tmp += j * dp[i+1][j-1][k]
            if k > 0:
                tmp += k * dp[i][j+1][k-1]
            dp[i][j][k] = tmp / (i + j + k)
print(dp[i][j][k])

Solution (Python):

from functools import lru_cache
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_j
J - Sushi / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 枚の皿があります。 皿には 1,2,…,N と番号が振られています。 
最初、各 i (1≤i≤N) について、皿 i には ai (1≤ai≤3) 個の
    寿司が置かれています。
すべての寿司が無くなるまで、太郎君は次の操作を繰り返し行います。
1,2,…,N の目が等確率で出るサイコロを振り、出目を i とする。 
皿 i に寿司がある場合、皿 i の寿司を 1 個食べる。 
皿 i に寿司が無い場合、何も行わない。
すべての寿司が無くなるまでの操作回数の期待値を求めてください。

解説 :
「皿1に寿司が2個、皿2に寿司が1個」という状態と 
    「皿1に寿司が1個、皿2に寿司が2個」という状態だと、
        操作回数の期待値は同じ。
よく考えると、「どの皿に何個あるか」という
    ところまでわかる必要はなくて、
        「1個の皿がいくつ(c1)、2個の皿がいくつ(c2)、
            3個の皿がいくつ(c3)」だけで期待値は決まることがわかる。
すると結局

dp[c3][c2][c1] = 1 + 
    dp[c3][c2][c1 - 1] * (1の皿が選ばれる確率) + 
        dp[c3][c2 - 1][c1 + 1] * (2の皿が選ばれる確率) + 
            dp[c3 - 1][c2 + 1][c1] * (1の皿が選ばれる確率) + 
                dp[c3][c2][c1] * (0の皿が選ばれる確率) 

この確率漸化式になる
あとはdp[c3][c2][c1]を左辺に移行してごにょごにょして
dp[c3][c2][c1] = (n + 
    dp[c3][c2][c1 - 1] * c1 + 
        dp[c3][c2 - 1][c1 + 1] * c2 + 
            dp[c3 - 1][c2 + 1][c1] * c3) / (c1 + c2 + c3)
という遷移式を完成
メモ化再帰でもできるという噂があるがPythonはカスなので 
    いろいろと工夫する必要があります。
知見的には 
    ====================================
    | 期待値 = Σ ワンステップ前の期待値 * |
    |    そのステップになるための確率)    |
    ====================================
です。
"""

def solve():
    n = II()
    c = LI()
    c1, c2, c3 = [c.count(i) for i in range(1, 4)]
    d = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
    for i in range(c3 + 1):
        di = d[i]
        dim1 = d[i - 1]
        for j in range(c3 + c2 + 1 - i):
            dim1jp1 = dim1[j + 1]
            dijm1 = di[j - 1]
            dij = di[j]
            for k in range(c3 + c2 + c1 - i - j + 1):
                l = i + j + k
                if l == 0: continue
                res = n
                if i: res += i * dim1jp1[k]
                if j: res += j * dijm1[k + 1]
                if k: res += k * dij[k-1]
                dij[k] = res / l
    print(d[c3][c2][c1])
    return



if __name__ == '__main__':
    solve()

Solution (Python):

from functools import lru_cache
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

def solve():
    n = II()
    c = LI()
    c1, c2, c3 = [c.count(i) for i in range(1, 4)]
    d = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
    for i in range(c3 + 1):
        di = d[i]
        dim1 = d[i - 1]
        for j in range(c3 + c2 + 1 - i):
            dim1jp1 = dim1[j + 1]
            dijm1 = di[j - 1]
            dij = di[j]
            for k in range(c3 + c2 + c1 - i - j + 1):
                l = i + j + k
                if l == 0: continue
                res = n
                if i: res += i * dim1jp1[k]
                if j: res += j * dijm1[k + 1]
                if k: res += k * dij[k-1]
                dij[k] = res / l
    print(d[c3][c2][c1])
    return



if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = tuple(map(int, input().split()))

    
    
    

    I = 0
    J = 0
    K = 0
    for a in A:
        if a == 1:
            I += 1
        elif a == 2:
            J += 1
        else:
            K += 1

    dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)] 

    
    
    

    for k in range(K + 1):
        for j in range(K + J + 1 - k):
            for i in range(N + 1 - k  - j):
                if i == j == k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[k][j][i - 1]
                if j > 0:
                    tmp += j * dp[k][j - 1][i + 1]
                if k > 0:
                    tmp += k * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp / (i + j + k)

    print (dp[K][J][I])

    

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = tuple(map(int, input().split()))

    I = A.count(1)
    J = A.count(2)
    K = A.count(3)
    
    
    
    
    
    
    

    dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)] 

    
    
    

    for k in range(K + 1):
        for j in range(K + J + 1 - k):
            for i in range(N + 1 - k  - j):
                if i == j == k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[k][j][i - 1]
                if j > 0:
                    tmp += j * dp[k][j - 1][i + 1]
                if k > 0:
                    tmp += k * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp / (i + j + k)

    print (dp[K][J][I])

    

if __name__ == '__main__':
    main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[0.0] * (n+1) for i in range(n+1)] for i in range(n+1)]

for c in range(C+1):
  for b in range(B+C+1-c):
    for a in range(A+B+C+1-c-b):
      if a == b == c == 0:continue
      result = n
      result += (dp[a-1][b][c]*a if a-1 >= 0 else 0)
      result += (dp[a+1][b-1][c]*b if b-1 >= 0 else 0)
      result += (dp[a][b+1][c-1]*c if c-1 >= 0 else 0)
      dp[a][b][c]=result / (a+b+c)

print(dp[A][B][C])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
cnt=[0,0,0,0]
for a in A:
    cnt[a]+=1
aaa=cnt[1]
bbb=cnt[2]
ccc=cnt[3]

dp=[[[0]*(N+1) for j in range(bbb+ccc+1)] for i in range(ccc+1)]

for k in range(ccc+1):
    for j in range(bbb+ccc-k+1):
        for i in range(N-k-j+1):
            tmp=i+j+k
            if tmp==0:
                continue
            else:
                dp[k][j][i]=N/tmp
                if i>0:
                    dp[k][j][i]+=i*dp[k][j][i-1]/tmp
                if j>0:
                    dp[k][j][i]+=j*dp[k][j-1][i+1]/tmp
                if k>0:
                    dp[k][j][i]+=k*dp[k-1][j+1][i]/tmp
                
print(dp[ccc][bbb][aaa])

Solution (Python):
def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  a=c1+c2+c3+1
  b=c2+c3+1
  c=c3+1
  
  dp=[[[0]*a for _ in range(b)] for _ in  range(c)]
  
  for i in range(c):
    for j in range(b-i):
      for k in range(a-i-j):
        tmp=i+j+k
        if tmp==0:
          continue
        else:
          dp[i][j][k]=n/tmp
          if i>0:
            dp[i][j][k]+=i*dp[i-1][j+1][k]/tmp
          if j>0:
            dp[i][j][k]+=j*dp[i][j-1][k+1]/tmp
          if k>0:
            dp[i][j][k]+=k*dp[i][j][k-1]/tmp
  print(dp[c3][c2][c1])
             
if __name__=='__main__':
  main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno])

Solution (Python):
def main():
    from collections import Counter
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

    def prob(c1, c2, c3):
        if memo[c1][c2][c3] != -1.0:
            return

        ret = n
        if c1 > 0:
            ret += c1 * memo[c1 - 1][c2][c3]
        if c2 > 0:
            ret += c2 * memo[c1 + 1][c2 - 1][c3]
        if c3 > 0:
            ret += c3 * memo[c1][c2 + 1][c3 - 1]
        ret /= c1 + c2 + c3

        memo[c1][c2][c3] = ret
        return

    n = int(readline())
    *a, = map(int, readline().split())

    ctr = Counter(a)

    memo = [[[-1.0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]  
    memo[0][0][0] = 0.0

    for c3 in range(n + 1):
        for c2 in range(n - c3 + 1):
            for c1 in range(n - c2 - c3 + 1):
                prob(c1, c2, c3)

    print(memo[ctr[1]][ctr[2]][ctr[3]])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
a,b,c = c[1],c[2],c[3]
DP = [[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]

for i in range(c+1):
    for j in range(n-a-i+1):
        for k in range(n-i-j+1):
            if i+j+k:
                DP[i][j][k] = (i*DP[i-1][j+1][k] + j*DP[i][j-1][k+1] + k*DP[i][j][k-1] + n)/(i+j+k)
print(DP[c][b][a])

Solution (Python):
def main():
    n=int(input())
    A=[0]*3
    for i in map(int,input().split()):
        A[i-1]+=1
    dp=[[[0]*(n+2)for _ in range(n+2)]for __ in range(n+2)]
    for i in range(A[2]+1):
        for j in range(n-A[0]-i+1):
            for k in range(n-i-j+1):
                if i+j+k!=0:
                    dp[i][j][k]=(dp[i-1][j+1][k]*i+dp[i][j-1][k+1]*j+dp[i][j][k-1]*k+n)/(i+j+k)
    i,j,k=A
    print(dp[k][j][i])
main()

Solution (Python):
n=int(input())
A=[0]*3
for i in map(int,input().split()):
    A[i-1]+=1
dp=[[[0]*(n+2)for _ in range(n+2)]for __ in range(n+2)]
for i in range(A[2]+1):
    for j in range(n-A[0]-i+1):
        for k in range(n-i-j+1):
            if i+j+k!=0:
                dp[i][j][k]=(dp[i-1][j+1][k]*i+dp[i][j-1][k+1]*j+dp[i][j][k-1]*k+n)/(i+j+k)
i,j,k=A
print(dp[k][j][i])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
arr=limii()
    
I = arr.count(3)
J = arr.count(2)
K = arr.count(1)
    
dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
        for ___ in range(I+1)]
    
for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            tmp = 0
            if k > 0:
                tmp += (k/n)*dp[i][j][k-1]
            if j > 0:
                tmp += (j/n)*dp[i][j-1][k+1]
            if i > 0:
                tmp += (i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += (n/(i+j+k))*(1 + tmp)
    
print(dp[I][J][K])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
abc=[0,0,0]
for i in A:
    abc[i-1]+=1
    
total=sum(A)


dp=[[[0.0]*(N+1) for _ in range(N+1)] for i in range(N+1)]



for k in range(abc[2]+1):
    for j in range(abc[2]+abc[1]+1-k):
        for i in range(sum(abc)+1-j-k):
            if i==0 and j==0 and k==0:
                continue
            if i-1>=0:
                dp[i][j][k]+=dp[i-1][j][k]*i
            if j-1>=0:
                dp[i][j][k]+=dp[i+1][j-1][k]*j
            if k-1>=0:
                dp[i][j][k]+=dp[i][j+1][k-1]*k
            dp[i][j][k]+=N
            dp[i][j][k]/=(i+j+k)

print(dp[abc[0]][abc[1]][abc[2]])

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
lst_a = list(map(float, input().split()))
one, two , three = lst_a.count(1),lst_a.count(2),lst_a.count(3),

dp = [[[0.0 for _ in range(N+1)]for _ in range(N+1)]for _ in range(N+1)]

for k in range(three + 1):
    for j in range(two + three + 1  - k):
        for i in range(one + two + three + 1 - k -j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = 1.0 * N
            if i > 0 : 
            	tmp += dp[i-1][j][k] * i
            if j > 0 :
            	tmp += dp[i+1][j-1][k] * j
            if k > 0 :
            	tmp += dp[i][j+1][k-1] * k

            dp[i][j][k] = tmp / (i+j+k)

print(dp[one][two][three])

Solution (Python):
N = int(input())
A = input().split()
px = py = pz = 0
for a in A:
  if a == '1':
    px += 1
  elif a == '2':
    py += 1
  elif a == '3':
    pz += 1

nx = px + py + pz
ny = py + pz
nz = pz

dp = [[[0]*(nx+1) for y in range(ny+1)] for z in range(nz+1)]

for z in range(nz+1):
  for y in range(ny+1-z):
    for x in range(nx+1-z-y):
      if x == y == z == 0:
        continue
      
      else:
        s = x + y + z
        t = N/s
        if x > 0:
          t += dp[z][y][x-1]*x/s
        if y > 0:
          t += dp[z][y-1][x+1]*y/s
        if z > 0:
          t += dp[z-1][y+1][x]*z/s
        
        dp[z][y][x] += t


print(dp[pz][py][px])

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
d =dict()
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
B = 0
for a in As:
    B += (N+1)**(a-1)
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = i+j+k
            if i:
                E += (i*N)/(s0**2) + d[x-1]*(i/s0)
            if j:
                E += (j*N)/(s0**2) + d[x-N]*(j/s0)
            if k:
                E += (k*N)/(s0**2) + d[x-N**2-N]*(k/s0)
            d[x] = E
print(d[B])

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
d = dict()
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
def decode(x):
    return [(x // ((N+1)**i))%(N+1) for  i in range(3)]
B = 0
for a in As:
    B += (N+1)**(a-1)
d[0] = 0
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = N-i-j-k
            if i:
                E += (i*N)/((N-s0)**2) + d[x-1]*(i/(N-s0))
            if j:
                E += (j*N)/((N-s0)**2) + d[x-N]*(j/(N-s0))
            if k:
                E += (k*N)/((N-s0)**2) + d[x-N**2-N]*(k/(N-s0))
            d[x] = E
print(d[B])

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            tmp = 0
            if k > 0:
                tmp += (k/n)*dp[i][j][k-1]
            if j > 0:
                tmp += (j/n)*dp[i][j-1][k+1]
            if i > 0:
                tmp += (i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += (n/(i+j+k))*(1 + tmp)

print(dp[I][J][K])

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            tmp = 0
            if k-1 > -1:
                tmp += (n/(i+j+k))*(k/n)*dp[i][j][k-1]
            if j-1 > -1:
                tmp += (n/(i+j+k))*(j/n)*dp[i][j-1][k+1]
            if i-1 > -1:
                tmp += (n/(i+j+k))*(i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += n/(i+j+k) + tmp

print(dp[I][J][K])

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            if k-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j][k-1]
            if j-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i][j-1][k+1]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += n/(i+j+k)

print(dp[I][J][K])

Solution (Python):
n = int(input())
a = input().split()

c1 = a.count('1')
c2 = a.count('2')
c3 = a.count('3')

dp =[ [[0] * (n+1) for _ in range(c3+c2+1)] for __ in range(c3+1)]


for i in range(c3+1):
    for j in range(c3+c2+1-i):
        for k in range(n+1-i-j):
            if(i+j+k == 0):
                dp[i][j][k]=0
            else:
                temp = 0
                if(i > 0):
                    temp += dp[i-1][j+1][k] * i/(k+j+i)
                if(j > 0):
                    temp += dp[i][j-1][k+1] * j/(k+j+i)
                if(k > 0):
                    temp += dp[i][j][k-1] * k/(k+j+i)
                dp[i][j][k] = temp + n/(k+j+i)

print(dp[c3][c2][c1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

dp = [[[-1]*(cnt1 + cnt2 + cnt3 + 1) for _ in range(cnt2 + cnt3 + 1)] for _ in range(cnt3 + 1)]
dp[0][0][0] = 0
 
for c3 in range(cnt3 + 1):
    for c2 in range(cnt2 + cnt3 + 1 - c3):
        for c1 in range(cnt1 + cnt2 + cnt3 + 1 - c2 - c3):
            if c1 + c2 + c3 == 0:
                continue
            tmp = 0
            num = c1 + c2 + c3
            
            if c3 != 0:
                tmp += (c3 / n) * dp[c3-1][c2+1][c1]
            
            if c2 != 0:
                tmp += (c2 / n) * dp[c3][c2-1][c1+1]
            
            if c1 != 0:
                tmp += (c1 / n) * dp[c3][c2][c1-1]
            dp[c3][c2][c1] = n / num * (tmp + 1)

print(dp[cnt3][cnt2][cnt1])