Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i. 
All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box and the remaining n balls to the other box (Please read the explanation of the second example carefully).
Please note that the two boxes are considered different. For example, if we have two balls of colors a and b, and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a) (Please read the explanation of the first example carefully).
We want to calculate the probability that the two boxes have the same number of distinct balls.
 
Example 1:
Input: balls = [1,1]
Output: 1.00000
Explanation: Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

Example 2:
Input: balls = [2,1,1]
Output: 0.66667
Explanation: We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equale probability (i.e. 1/12):
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
After that we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667

Example 3:
Input: balls = [1,2,1,2]
Output: 0.60000
Explanation: The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6

Example 4:
Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3

Example 5:
Input: balls = [6,6,6,6,6,6]
Output: 0.90327

 
Constraints:

1 <= balls.length <= 8
1 <= balls[i] <= 6
sum(balls) is even.
Answers within 10^-5 of the actual value will be accepted as correct.

Difficulty: interview

Starter code:

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        

Solutions:
from math import comb


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        n = len(balls)
        s = sum(balls)
        s2 = s // 2

        @lru_cache(None)
        def count(index, delta, ca):
            if index == n: return 1 if delta == 0 and ca == s2 else 0
            total = sum([count(index + 1, delta, ca + x) * comb(balls[index], x) for x in range(1, balls[index])])
            total += count(index + 1, delta + 1, ca)
            total += count(index + 1, delta - 1, ca + balls[index])
            return total

        return count(0, 0, 0) / comb(s, s // 2)


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        @lru_cache(None)
        def select(n, r):
            if r > n:
                return 0
            if  r == 0:
                return 1
            if r == 1:
                return n
            return select(n-1, r) + select(n-1, r-1)
        
        @lru_cache(None)
        def dputil(i, j, pos, n):
            if pos == -1:
                if n == 0:
                    return 1
                else:
                    return 0
            p2 = 1<<pos
            if i&p2 and j&p2:
                ans = 0
                for x in range(1, balls[pos]):
                    diff = n - 2*x + balls[pos]
                    ans += dputil(i, j, pos-1, diff)*select(balls[pos], x)
                return ans
            if i&p2:
                return dputil(i, j, pos-1, n-balls[pos])
            else:
                return dputil(i, j, pos-1, n+balls[pos])
        
        def numsplits(n):
            cnt = 0
            while n:
                cnt += n%2
                n = n//2
            return cnt
        
        k = len(balls)
        tot = sum(balls)
        k2 = 1<<k
        valid = 0
        for i in range(k2):
            for j in range(k2):
                if (i|j != k2-1) or numsplits(i) != numsplits(j):
                    continue
                valid += dputil(i, j, k-1, 0)
        return float(valid)/float(select(tot, tot//2))


from math import factorial


def choose(n, k):
    return factorial(n)//(factorial(n - k) * factorial(k))

def allPossibilities(balls):
    n = sum(balls)
    
    total = factorial(n)
    
    for b in balls:
        total //= factorial(b)
        
    return total

def count(balls, balance, a, b, i):
    c = balls[i]
    
    upper = min(c, a)
    lower = max(c - b, 0)
    
    tempBalance = balance
    
    total = 0
    
    for j in range(lower, upper + 1):
        balance = tempBalance
        if j == 0:
            balance -= 1
        if j == c:
            balance += 1
        if i == len(balls) - 1:
            if balance == 0:
                return 1
            else:
                return 0
        else:
            total += choose(a, j) * choose(b, c - j) * count(balls, balance, a - j, b - c + j, i + 1)
            
    return total

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        return count(balls, 0, sum(balls) // 2, sum(balls) // 2, 0) / allPossibilities(balls)


from math import comb, prod
from itertools import accumulate

class Solution:
  def getCombinations(self, balls, l, r, d):
    # l, r: number of available position on left and right,
    # d: difference of number of distinct color on left and right.
    if not balls:
      return d == 0
    if abs(d) > len(balls):
      return 0
    x, count = balls.pop(), 0
    for i in range(x + 1):
      if l >= i and r >= x - i:
        count += comb(l, i) * comb(r, x - i) * self.getCombinations(
          balls.copy(), l - i, r - (x - i), d - (i == 0) + (i == x)
        )
    return count
  def getProbability(self, balls: List[int]) -> float:
    n = sum(balls)
    total = prod(comb(n, x) for n, x in zip(accumulate(balls), balls))
    count = self.getCombinations(balls, n // 2, n // 2, 0)
    return count / total

import functools as ft
import math
import operator


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.total = 0
        self.valid = 0
        self.balls = balls
        self.k = len(balls)
        self.n = sum(balls) // 2
        self.ball_sums = [sum(balls[index :]) for index in range(self.k + 1)]
        self.update([], 0, 0)
        return self.valid / self.total
    
    @ft.lru_cache(None)
    def factorial(self, n: int) -> int:
        return math.factorial(n)

    @ft.lru_cache(None)
    def count(self, *balls: int) -> int:
        return self.factorial(self.n) // ft.reduce(operator.mul, map(self.factorial, balls))
    
    def update(self, left_balls: List[int], total: int, delta: int) -> None:
        if len(left_balls) == self.k:
            if total != self.n:
                return
            right_balls = [total_cnt - left_cnt for left_cnt, total_cnt in zip(left_balls, self.balls)]
            count = self.count(*sorted(left_balls)) * self.count(*sorted(right_balls))
            self.total += count
            if delta == 0:
                self.valid += count
            return
        index = len(left_balls)
        if total + self.ball_sums[index] < self.n:
            return
        if total > self.n:
            return
        if index == self.k - 1:
            new_delta = delta + (self.n - total == self.balls[index]) - (self.n - total == 0)
            self.update(left_balls + [self.n - total], self.n, new_delta)
            return
        for cnt in range(self.balls[index] + 1):
            new_delta = delta + (cnt == self.balls[index]) - (cnt == 0)
            self.update(left_balls + [cnt], total + cnt, new_delta)

import math
class Solution:
    def Prob(self, balls: List[int], left: int, right: int, diff: int) -> float:
        if len(balls) == 1:
            return 1 if (left*right != 0 and diff == 0) or (left == 0 and diff == -1) or (right == 0 and diff == 1) else 0
        a = balls[-1]
        p = [float(math.comb(a,i)*math.prod(range(left-i+1, left+1))*math.prod(range(right-a+i+1, right+1)))/math.prod(range(left+right-a+1, left+right+1)) for i in range(a+1)]
        A = [self.Prob(balls[:-1], left, right-a,diff+1)] + [self.Prob(balls[:-1], left-i, right-a+i,diff) for i in range(1,a)] + [self.Prob(balls[:-1], left-a, right,diff-1)]
        S = sum(p[i]*A[i] for i in range(a+1))
        return S
    def getProbability(self, balls: List[int]) -> float:
        return self.Prob(balls, sum(balls)//2, sum(balls)//2, 0)

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        '''
        箱子中有n个球，箱中有2种颜色的球，分别有k1,k2个
        箱子中的组合数为n!/k1!k2!
        '''
        n=sum(balls)  #总球数
        k=len(balls)  #球色数
        total=0
        valid=0
        fact=[1]*50   #得到每个数的阶乘
        for i in range(1,50):
            fact[i]=fact[i-1]*i
        #d: depth
        #b1, b2: # of balls in box1, box2
        #c1,c2 :两个box中不同色的球数
        #p1, p2: # permutations of duplicate balls in box1, box2
        def dfs(d,b1,b2,c1,c2,p1,p2):
            nonlocal total
            nonlocal valid
            #两个盒子中球数要相同
            if b1>n//2 or b2>n//2:
                return
            if d==k:
                count=fact[b1]/ p1*fact[b2]/ p2
                #此时的组合总数
                #判断是否符合所要求的
                total+=count
                valid+=count*(c1==c2)
                return
            for s1 in range(balls[d]+1):
                s2=balls[d]-s1
                dfs(d+1,b1+s1,b2+s2,c1+(s1>0),c2+(s2>0),p1*fact[s1],p2*fact[s2])
        dfs(0,0,0,0,0,1,1)
        return valid/total

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        N = len(balls)
        sm = sum(balls)
        half = sm // 2
        
        @lru_cache(None)
        def rec2(cur, na, nb):
            if na > half or nb > half:
                return 0
            if cur == N:
                return int(na == nb)
            
            ans = 0
            for i in range(balls[cur]+1):
                remplacea, remplaceb = (half - na), (half-nb)
                choice = math.comb(remplacea, i) * math.comb(remplaceb, balls[cur] - i)
                ans += rec2(cur+1, na + i, nb + balls[cur] - i) * choice
            
            return ans
        
        
        @lru_cache(None)
        def rec(cur, na, nb, uniquea, uniqueb):
            if na > half or nb > half:
                return 0
            if cur == N:
                # print(na, nb, uniquea, uniqueb)
                if na != nb or uniquea != uniqueb:
                    return 0
                # print(uniquea, uniqueb)
                return 1
            
            gg = 0
            for i in range(balls[cur]+1):
                toa, tob = na+i, nb + balls[cur] - i
                ua, ub = uniquea + int(i > 0), uniqueb + int(balls[cur] - i > 0)
                
                remplacea, remplaceb = (half - na), (half-nb)
                choice = math.comb(remplacea, i) * math.comb(remplaceb, balls[cur] - i)
                gg += rec(cur+1, toa, tob, ua, ub) * choice
                
            return gg
        
        gg = rec(0, 0, 0, 0, 0)
        permutation = math.factorial(sm)/math.factorial(half)
        al = rec2(0,0,0)
        return gg/al

from math import factorial as fac
from itertools import product

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        
        def ways(nums):
            tmp = fac(sum(nums))
            for num in nums:
                tmp //= fac(num)
            return tmp
        
        half = sum(balls)//2
        n = len(balls)
        res = 0
        stack = [list(range(ball+1)) for ball in balls]
        comb = list(product(*stack))
        
        for i in range(len(comb)):
            if sum( comb[i] ) == half and comb[i].count(0) == comb[-i-1].count(0):
                res += ways(comb[i]) * ways(comb[-i-1])
                
        return res / ways(balls)                
        
        

        
        


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        @lru_cache(None)
        def C(n, m):
            # c = 1
            # for i in range(n, n - m, -1):
            #     c *= i
            return math.factorial(n) / math.factorial(m) / math.factorial(n - m)
        
        # @lru_cache(None)
        def choose(i, k, d1, d2, cnt):
            if k == 0 and i <= n:
                return cnt, (cnt if d1 == d2 + n - i else 0)
            if k < 0 or i == n:
                return 0, 0
            total = 0
            equal = 0
            for j in range(balls[i] + 1):
                if k - j < 0:
                    break
                t, e = choose(i + 1, k - j, d1 + (1 if j > 0 else 0), d2 + (1 if j < balls[i] else 0), cnt * C(balls[i], j))
                total += t
                equal += e
            return total, equal
        
        n = len(balls)
        k = sum(balls)
        t, e = choose(0, k // 2, 0, 0, 1)
        return e / t
            


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        n=sum(balls)  #总球数
        k=len(balls)  #球色数
        self.total=self.valid=0
        fact=[1]*50   #得到每个数的阶乘
        for i in range(1,50):
            fact[i]=fact[i-1]*i
        #d: depth
        #b1, b2: # of balls in box1, box2
        #c1,c2 :两个box中不同色的球数
        #p1, p2: # permutations of duplicate balls in box1, box2
        def dfs(d,b1,b2,c1,c2,p1,p2):
            if b1>n//2 or b2>n//2:
                return
            if d==k:
                count=fact[b1] / p1 * fact[b2] / p2
                self.total+=count
                self.valid+=count*(c1==c2)
                return
            for s1 in range(balls[d]+1):
                s2=balls[d]-s1
                dfs(d+1,b1+s1,b2+s2,c1+(s1>0),c2+(s2>0),p1*fact[s1],p2*fact[s2])
        dfs(0,0,0,0,0,1,1)
        return self.valid/self.total

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        '''
        箱子中有n个球，箱中有2种颜色的球，分别有k1,k2个
        箱子中的组合数为n!/k1!k2!
        '''
        n=sum(balls)  #总球数
        k=len(balls)  #球色数
        self.total=self.valid=0
        fact=[1]*50   #得到每个数的阶乘
        for i in range(1,50):
            fact[i]=fact[i-1]*i
        #d: depth
        #b1, b2: # of balls in box1, box2
        #c1,c2 :两个box中不同色的球数
        #p1, p2: # permutations of duplicate balls in box1, box2
        def dfs(d,b1,b2,c1,c2,p1,p2):
            if b1>n//2 or b2>n//2:
                return
            if d==k:
                count=fact[b1]/ p1*fact[b2]/ p2
                self.total+=count
                self.valid+=count*(c1==c2)
                return
            for s1 in range(balls[d]+1):
                s2=balls[d]-s1
                dfs(d+1,b1+s1,b2+s2,c1+(s1>0),c2+(s2>0),p1*fact[s1],p2*fact[s2])
        dfs(0,0,0,0,0,1,1)
        return self.valid/self.total

from math import factorial as fac

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        
        def ways(nums):
            tmp = fac(sum(nums))
            for num in nums:
                tmp //= fac(num)
            return tmp
        
        def dist(pos, rem):
            if pos == len(balls):
                if rem == 0:
                    isValid()
                return 
            for i in range( min(balls[pos], rem)+1 ):
                a[pos] = i
                b[pos] = balls[pos] - i
                dist(pos + 1, rem - i)
    
        def isValid():
            x = y = 0
            x = sum(1 for i in a if i > 0)
            y = sum(1 for j in b if j > 0)
            if x == y:
                self.res += ways(a) * ways(b)
        
        total = sum(balls)
        n = len(balls)
        a = [0] * n
        b = [0] * n
        self.res = 0
        dist(0, total//2)
        return self.res / ways(balls)
        
        


from typing import List


# May 30 - May 31, 2002
# Reviewed: Sep 9, 2020. This is a math + dfs problem.
class Solution:
    def combination(self, N, K) -> int:
        res = 1
        for i in range(N, max(K, N - K), -1):
            res *= i
        for i in range(2, min(K, N - K) + 1):
            res /= i
        return res

    def getProbability(self, balls: List[int]) -> float:
        total = sum(balls)
        result = 0

        def dfs(spaceA: int, spaceB: int, colorsA: int, colorsB: int, remainBalls: List[int], probability: float):
            nonlocal result
            if not remainBalls:
                if colorsA == colorsB:
                    result += probability
                return

            currentBallCount = remainBalls[0]

            # The total number of ways to distribute the balls in the the boxes
            c_overall = self.combination(spaceA + spaceB, currentBallCount)

            # For the `currentBallCount`, assume i of them goes to box A and the rest goes to box B.
            # We need:
            # 1) `currentBallCount - i` to be within range of [0, spaceB], which give,
            #
            #     0 <= currentBallCount - i <= spaceB
            #     currentBallCount - spaceB <= i <= currentBallCount
            #
            # 2) i to be within range [0, spaceA]
            #
            # The overall range is [max(currentBallCount - spaceB), min(currentBallCount, spaceA)].
            for i in range(max(currentBallCount - spaceB, 0), min(currentBallCount, spaceA) + 1):
                j = currentBallCount - i

                # count the number of ways for i ball to go into box A and j balls to go into box B
                c1 = self.combination(spaceA, i)
                c2 = self.combination(spaceB, j)

                p = c1 * c2 / c_overall

                dfs(
                    spaceA=spaceA - i,
                    spaceB=spaceB - j,
                    colorsA=colorsA + (i != 0),
                    colorsB=colorsB + (j != 0),
                    remainBalls=remainBalls[1:],
                    probability=probability * p
                )

        dfs(spaceA=total // 2, spaceB=total // 2, colorsA=0, colorsB=0, remainBalls=balls, probability=1)
        return result


s = Solution()
print((s.getProbability([1, 1])))  # 1.0
print((s.getProbability([2, 1, 1])))  # 0.666666666
print((s.getProbability([1, 2, 1, 2])))  # 0.6
print((s.getProbability([6, 6, 6, 6, 6, 6])))  # 0.90327


from collections import defaultdict as dt
class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.total = self.valid = 0
        fact = [1] * 50
        for i in range(1, len(fact)):
            fact[i] = fact[i-1] * i

        def run(b1, b2, c1, c2, p, idx, n):
            if b1 > n/2 or b2 > n/2: return
            if idx == len(balls):
                # times = fact[b1] / p1 * fact[b2] / p2
                self.total += p
                self.valid += p * int(c1 == c2)
            else:
                for x in range(balls[idx]+1):
                    run(
                        b1+x, 
                        b2+(balls[idx]-x),
                        c1+int(x>0),
                        c2+int((balls[idx]-x)>0),
                        p / fact[x] / fact[balls[idx]-x],
                        idx+1,
                        n
                    )
        
        run(0,0,0,0,1.0, 0, sum(balls))
        return self.valid/self.total

from math import factorial as fac

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        
        def ways(nums):
            tmp = fac(sum(nums))
            for num in nums:
                tmp //= fac(num)
            return tmp
        
        def dist(pos, rem):
            if rem < 0:
                return
            if pos == len(balls):
                if rem == 0:
                    isValid()
                return 
            for i in range( min(balls[pos], rem)+1 ):
                a[pos] = i
                b[pos] = balls[pos] - i
                dist(pos + 1, rem - i)
    
        def isValid():
            x = y = 0
            x = sum(1 for i in a if i > 0)
            y = sum(1 for j in b if j > 0)
            if x == y:
                self.res += ways(a) * ways(b)
        
        total = sum(balls)
        n = len(balls)
        a = [0] * n
        b = [0] * n
        self.res = 0
        dist(0, total//2)
        return self.res / ways(balls)
        
        


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        @lru_cache(None)
        def C(n, m):
            if m > n // 2:
                return C(n, n - m)
            return math.factorial(n) / math.factorial(m) / math.factorial(n - m)
        
        @lru_cache(None)
        def choose(i, k, d1, d2, cnt):
            if k == 0 and i <= n:
                return cnt, (cnt if d1 == d2 + n - i else 0)
            if k < 0 or i == n:
                return 0, 0
            total = 0
            equal = 0
            for j in range(balls[i] + 1):
                if k - j < 0:
                    break
                t, e = choose(i + 1, k - j, d1 + (1 if j > 0 else 0), d2 + (1 if j < balls[i] else 0), cnt * C(balls[i], j))
                total += t
                equal += e
            return total, equal
        
        n = len(balls)
        k = sum(balls)
        t, e = choose(0, k // 2, 0, 0, 1)
        return e / t
            


from collections import defaultdict as dt
class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.total = self.valid = 0
        fact = [1] * 50
        for i in range(1, len(fact)):
            fact[i] = fact[i-1] * i

        def run(b1, b2, c1, c2, p1, p2, idx, n):
            if b1 > n/2 or b2 > n/2: return
            if idx == len(balls):
                times = fact[b1] / p1 * fact[b2] / p2
                self.total += times
                self.valid += times * int(c1 == c2)
            else:
                for x in range(balls[idx]+1):
                    run(
                        b1+x, 
                        b2+(balls[idx]-x),
                        c1+int(x>0),
                        c2+int((balls[idx]-x)>0),
                        p1 * fact[x],
                        p2 * fact[balls[idx]-x],
                        idx+1,
                        n
                    )
        
        run(0,0,0,0,1.0,1.0, 0, sum(balls))
        return self.valid/self.total

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.total = 0
        self.valid = 0
        t = sum(balls) >> 1
        n = len(balls)
        def check(s):
            return sum([x != 0 for x in s]) == sum([balls[i] - s[i] != 0 for i in range(n)])
        fac = [1]
        for i in range(1, t + 1):
            fac.append(fac[-1] * i)
        def update(s):
            x = y = fac[-1]
            cnt1 = cnt2 = 0
            for i, c in enumerate(s):
                x //= fac[c]
                y //= fac[balls[i] - c]
                cnt1 += (c > 0)
                cnt2 += (balls[i] - c > 0)
            ret = x * y
            self.total += ret
            if cnt1 == cnt2:
                self.valid += ret
        def dfs(state, i):
            s, cnt = state
            if cnt == t:
                update(s)
                return 
            if i == n: return
            for x in range(balls[i] + 1):
                if cnt + x > t: break
                s[i] = x
                dfs((s, cnt + x), i + 1)
                s[i] = 0
        s = [0] * n
        dfs((s, 0), 0)
        print(self.valid)
        print(self.total)
        return self.valid / self.total

from collections import defaultdict as dt
class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.total = self.valid = 0
        fact = [1] * 50
        for i in range(1, len(fact)):
            fact[i] = fact[i-1] * i

        def run(b1, b2, c1, c2, p, idx, n):
            if b1 > n/2 or b2 > n/2: return
            if idx == len(balls):
                # times = fact[b1] / p1 * fact[b2] / p2
                self.total += p * int(b1 == b2)
                self.valid += p * int(b1 == b2) * int(c1 == c2)
            else:
                for x in range(balls[idx]+1):
                    run(
                        b1+x, 
                        b2+(balls[idx]-x),
                        c1+int(x>0),
                        c2+int((balls[idx]-x)>0),
                        p / fact[x] / fact[balls[idx]-x],
                        idx+1,
                        n
                    )
        
        run(0,0,0,0,1.0, 0, sum(balls))
        return self.valid/self.total

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        '''
        箱子中有n个球，箱中有2种颜色的球，分别有k1,k2个
        箱子中的组合数为n!/k1!k2!
        每次选取同一色彩的所有球分开放入两个盒子中
        '''
        k=len(balls)  #总色彩数
        n=sum(balls)  #总球数
        total=0   #总组合数
        valid=0   #符合条件总数
        fact=[1]*50
        for i in range(1,50):
            fact[i]=i*fact[i-1]
        
        def dfs(d,b1,b2,c1,c2,p1,p2):
            nonlocal total
            nonlocal valid
            if b1>n//2 or b2>n//2:
                return
            if d==k:
                count=fact[b1]/p1*fact[b2]/p2
                total+=count
                valid+=count*(c1==c2)
                return
            for s1 in range(balls[d]+1):
                s2=balls[d]-s1
                dfs(d+1,b1+s1,b2+s2,c1+(s1>0),c2+(s2>0),p1*fact[s1],p2*fact[s2])
        dfs(0,0,0,0,0,1,1)
        return valid/total


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        '''
        箱子中有n个球，箱中有2种颜色的球，分别有k1,k2个
        箱子中的组合数为n!/k1!k2!
        '''
        n=sum(balls)  #总球数
        k=len(balls)  #球色数
        self.total=0
        self.valid=0
        fact=[1]*50   #得到每个数的阶乘
        for i in range(1,50):
            fact[i]=fact[i-1]*i
        #d: depth
        #b1, b2: # of balls in box1, box2
        #c1,c2 :两个box中不同色的球数
        #p1, p2: # permutations of duplicate balls in box1, box2
        def dfs(d,b1,b2,c1,c2,p1,p2):
            if b1>n//2 or b2>n//2:
                return
            if d==k:
                count=fact[b1]/ p1*fact[b2]/ p2
                self.total+=count
                self.valid+=count*(c1==c2)
                return
            for s1 in range(balls[d]+1):
                s2=balls[d]-s1
                dfs(d+1,b1+s1,b2+s2,c1+(s1>0),c2+(s2>0),p1*fact[s1],p2*fact[s2])
        dfs(0,0,0,0,0,1,1)
        return self.valid/self.total

import functools as ft
import math
import operator


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.total = 0
        self.valid = 0
        self.balls = balls
        self.k = len(balls)
        self.n = sum(balls) // 2
        self.ball_sums = [sum(balls[index :]) for index in range(self.k + 1)]
        self.update([], 0, 0)
        return self.valid / self.total
    
    @ft.lru_cache(None)
    def factorial(self, n: int) -> int:
        return math.factorial(n)
    
    def count(self, balls: List[int]) -> int:
        return self.factorial(self.n) // ft.reduce(operator.mul, map(self.factorial, balls))
    
    def update(self, left_balls: List[int], total: int, delta: int) -> None:
        if len(left_balls) == self.k:
            if total != self.n:
                return
            right_balls = [total_cnt - left_cnt for left_cnt, total_cnt in zip(left_balls, self.balls)]
            count = self.count(left_balls) * self.count(right_balls)
            self.total += count
            if delta == 0:
                self.valid += count
            return
        index = len(left_balls)
        if total + self.ball_sums[index] < self.n:
            return
        if total > self.n:
            return
        if index == self.k - 1:
            new_delta = delta + (self.n - total == self.balls[index]) - (self.n - total == 0)
            self.update(left_balls + [self.n - total], self.n, new_delta)
            return
        for cnt in range(self.balls[index] + 1):
            new_delta = delta + (cnt == self.balls[index]) - (cnt == 0)
            self.update(left_balls + [cnt], total + cnt, new_delta)

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        '''
        箱子中有n个球，箱中有2种颜色的球，分别有k1,k2个
        箱子中的组合数为n!/k1!k2!
        '''
        n=sum(balls)  #总球数
        k=len(balls)  #球色数
        self.total=self.valid=0
        fact=[1]*50   #得到每个数的阶乘
        for i in range(1,50):
            fact[i]=fact[i-1]*i
        #d: depth
        #b1, b2: # of balls in box1, box2
        #c1,c2 :两个box中不同色的球数
        #p1, p2: # permutations of duplicate balls in box1, box2
        def dfs(d,b1,b2,c1,c2,p1,p2):
            if b1>n//2 or b2>n//2:
                return
            if d==k:
                count=math.factorial(b1)/ p1 * math.factorial(b2)/ p2
                self.total+=count
                self.valid+=count*(c1==c2)
                return
            for s1 in range(balls[d]+1):
                s2=balls[d]-s1
                dfs(d+1,b1+s1,b2+s2,c1+(s1>0),c2+(s2>0),p1*math.factorial(s1),p2*math.factorial(s2))
        dfs(0,0,0,0,0,1,1)
        return self.valid/self.total

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        
        total = sum(balls)
        k = len(balls)
        
        def theSame(added):
            res = 0
            for i in range(k):
                if added[i] == 0:
                    res -= 1
                elif balls[i] == added[i]:
                    res += 1
            return res == 0
        
        
        def combination(this, pick):
            pick = min(this-pick, pick)
            res = 1
            i = this
            j = 1
            while i > pick:
                res *= i
                res /= j
                i -= 1
                j += 1
            return res
            
        def helper(i, added, cur):
            
            if cur == total // 2:
               
                if theSame(added):
                    res = 1
                    for i in range(k):
                        res *= combination(balls[i], added[i])
                    return res
                return 0
            if i == k:
                return 0
            if cur > total // 2:
                return 0
            res = 0
            for t in range(balls[i]+1):
                added[i] = t
                res += helper(i+1, added, cur+t) 
            added[i] = 0
            return res
        
        added = [0] * k 
        return helper(0, added, 0) / combination(total, total // 2)
        
        
            
                          
                           
                        
                
                    
        
                
                
        
        
        


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        def calc(d):
            n = len(d)
            s = sum(d.values())
            result = math.factorial(s)
            for k, v in list(d.items()):
                result /= math.factorial(v)
            return result
        
        t, e = 0, 0
        def choose(i, k, d1, d2):
            nonlocal t
            nonlocal e
            if k == 0 and i <= n:
                for j in range(i, n):
                    d2[j] = balls[j]
                t_ = calc(d1) * calc(d2)
                t += t_
                e += t_ if len(d1) == len(d2) else 0
                return 
            if k < 0 or i == n:
                return
            for j in range(balls[i] + 1):
                if k - j < 0:
                    break
                if j > 0:
                    d1[i] = j
                if balls[i] - j > 0:
                    d2[i] = balls[i] - j
                else:
                    d2.pop(i)
                choose(i + 1, k - j, d1, d2)
            if i in d1:
                d1.pop(i)
            if i in d2:
                d2.pop(i)
        
        n = len(balls)
        k = sum(balls) // 2
        choose(0, k, {}, {})
        # print(t, e)
        return e / t
            


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        def calc(d):
            n = len(d)
            s = sum(d.values())
            result = math.factorial(s)
            facs = {}
            for k, v in list(d.items()):
                result /= math.factorial(v)
            return result
        
        t, e = 0, 0
        def choose(i, k, d1, d2):
            nonlocal t
            nonlocal e
            if k == 0 and i <= n:
                for j in range(i, n):
                    d2[j] = balls[j]
                t_ = calc(d1) * calc(d2)
                t += t_
                e += t_ if len(d1) == len(d2) else 0
                return 
            if k < 0 or i == n:
                return
            for j in range(balls[i] + 1):
                if k - j < 0:
                    break
                if j > 0:
                    d1[i] = j
                if balls[i] - j > 0:
                    d2[i] = balls[i] - j
                else:
                    d2.pop(i)
                choose(i + 1, k - j, d1, d2)
            if i in d1:
                d1.pop(i)
            if i in d2:
                d2.pop(i)
        
        n = len(balls)
        k = sum(balls) // 2
        choose(0, k, {}, {})
        # print(t, e)
        return e / t
            


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        def C(n, m):
            c = 1
            for i in range(n, n - m, -1):
                c *= i
            return c / math.factorial(m)
        
        t, e = 0, 0
        def choose(i, k, d1, d2):
            nonlocal t, e
            if k == 0 and i <= n:
                for j in range(i, n):
                    d2[j] = balls[j]
                t_ = 1
                for k, v in list(d1.items()):
                    t_ *= C(balls[k], v)
                t += t_
                e += t_ if len(d1) == len(d2) else 0
                return 
            if k < 0 or i == n:
                return
            for j in range(balls[i] + 1):
                if k - j < 0:
                    break
                if j > 0:
                    d1[i] = j
                if balls[i] - j > 0:
                    d2[i] = balls[i] - j
                else:
                    d2.pop(i)
                choose(i + 1, k - j, d1, d2)
            if i in d1:
                d1.pop(i)
            if i in d2:
                d2.pop(i)
        
        n = len(balls)
        k = sum(balls)
        choose(0, k // 2, {}, {})
        # print(t, e)
        return e / t
            


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        balls_flattened = []
        for i, count in enumerate(balls):
            balls_flattened.extend([i] * count)
        
        def has_same_distinct_color(perm):
            n = len(perm)
            return len(set(perm[: n // 2])) == len(set(perm[n // 2 :]))
        
        total = [0]
        same_distinct_color = [0]
        def get_perm(cur, balls):
            if not balls:
                total[0] += 1
                same_distinct_color[0] += has_same_distinct_color(cur)
                return
            for i in range(len(balls)):
                if i > 0 and balls[i] == balls[i - 1]:
                    continue
                get_perm(cur + [balls[i]], balls[:i] + balls[i + 1 :])
        
        get_perm([], balls_flattened)
        return same_distinct_color[0] / total[0]
    

    def getProbability(self, balls: List[int]) -> float:
        
        factorial_cache = [1]
        for i in range(1, sum(balls) + 1):
            factorial_cache.append(factorial_cache[-1] * i)
                
        def get_perm_count(arr):
            total = factorial_cache[sum(arr)]
            for a in arr:
                total //= factorial_cache[a]
            return total
        
        total_perms = get_perm_count(balls)
        valid_perms = [0]
        
        def find_valid_split(n, start, distinct1, group1, distinct2, group2):
            if n == 0:
                if distinct1 == distinct2:
                    valid_perms[0] += get_perm_count(group1) * get_perm_count(group2)
                return
            
            for i in range(start, len(group1)):
                if group1[i] == 0:
                    continue
                
                new_num1 = group1[i] - 1
                new_distinct1 = distinct1 if new_num1 > 0 else distinct1 - 1
                new_num2 = group2[i] + 1
                new_distinct2 = distinct2 if new_num2 > 1 else distinct2 + 1
                if new_distinct1 < new_distinct2:
                    continue
                    
                new_group1 = group1[:i] + [new_num1] + group1[i + 1 :]
                new_group2 = group2[:i] + [new_num2] + group2[i + 1 :]
                find_valid_split(n - 1, i, new_distinct1, new_group1, new_distinct2, new_group2)
        
        find_valid_split(sum(balls) // 2, 0, len(balls), balls, 0, [0] * len(balls))
        return valid_perms[0] / total_perms
                

                
                
                


import math
from functools import lru_cache
from typing import List

class Solution:
  def getProbability(self, balls: List[int]) -> float:
    M = len(balls)
    N = sum(balls)
    F = [math.factorial(n) for n in range(N // 2 + 1)]

    s1 = [0] * M
    s2 = [0] * M

    def find(i):
      if i == M:
        if sum(s1) == sum(s2) and len([n for n in s1 if n]) == len([n for n in s2 if n]):
          base1 = F[N // 2] // math.prod(F[n] for n in s1)
          base2 = F[N // 2] // math.prod(F[n] for n in s2)
          return base1 * base2
        return 0

      s = 0
      for n in range(balls[i] + 1):
        s1[i] = n
        s2[i] = balls[i] - n
        s += find(i + 1)
      return s

    base = math.factorial(N) // math.prod(math.factorial(n) for n in balls)
    return find(0) / base

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        M = len(balls)
        N = sum(balls)
        F = [math.factorial(n) for n in range(N// 2 + 1)]
        s1 = [0] * M
        s2 = [0] * M
        
        def find(i):
            if i == M:
                if sum(s1) == sum(s2) and len([n for n in s1 if n]) == len([n for n in s2 if n]):
                    base1 = F[N//2] // math.prod(F[n] for n in s1)
                    base2 = F[N//2] // math.prod(F[n] for n in s2)
                    return base1 * base2
                return 0
            
            s = 0
            for n in range(balls[i] + 1):
                s1[i] = n
                s2[i] = balls[i] - n
                s += find(i + 1)
            return s
    
        base = math.factorial(N) // math.prod(math.factorial(n) for n in balls)
        return find(0) / base

class Solution:
    # Brute force: check all permutations
    # O(n! / (ball_count! ^ k)) time, O(n) space 
    def getProbability(self, balls: List[int]) -> float:
        balls_flattened = []
        for i, count in enumerate(balls):
            balls_flattened.extend([i] * count)
        
        def has_same_distinct_color(perm):
            n = len(perm)
            return len(set(perm[: n // 2])) == len(set(perm[n // 2 :]))
        
        total = [0]
        same_distinct_color = [0]
        def get_perm(cur, balls):
            if not balls:
                total[0] += 1
                same_distinct_color[0] += has_same_distinct_color(cur)
                return
            for i in range(len(balls)):
                if i > 0 and balls[i] == balls[i - 1]:
                    continue
                get_perm(cur + [balls[i]], balls[:i] + balls[i + 1 :])
        
        get_perm([], balls_flattened)
        return same_distinct_color[0] / total[0]
    
    # Permutations of combinations
    # O(ball_count ^ k) time (put 0, 1, 2, ..., ball_count balls into box 1, and do it for k colors)
    # O(k) space for recursion and O(n) space for factorials
    def getProbability(self, balls: List[int]) -> float:
        
        factorial_cache = [1]
        for i in range(1, sum(balls) + 1):
            factorial_cache.append(factorial_cache[-1] * i)
                
        def get_perm_count(arr):
            total = factorial_cache[sum(arr)]
            for a in arr:
                total //= factorial_cache[a]
            return total
        
        total_perms = get_perm_count(balls)
        valid_perms = [0]
        
        def find_valid_split(n, start, distinct1, group1, distinct2, group2):
            if n == 0:
                if distinct1 == distinct2:
                    valid_perms[0] += get_perm_count(group1) * get_perm_count(group2)
                return
            
            for i in range(start, len(group1)):
                if group1[i] == 0:
                    continue
                
                new_num1 = group1[i] - 1
                new_distinct1 = distinct1 if new_num1 > 0 else distinct1 - 1
                new_num2 = group2[i] + 1
                new_distinct2 = distinct2 if new_num2 > 1 else distinct2 + 1
                if new_distinct1 < new_distinct2:
                    continue
                    
                new_group1 = group1[:i] + [new_num1] + group1[i + 1 :]
                new_group2 = group2[:i] + [new_num2] + group2[i + 1 :]
                find_valid_split(n - 1, i, new_distinct1, new_group1, new_distinct2, new_group2)
        
        find_valid_split(sum(balls) // 2, 0, len(balls), balls, 0, [0] * len(balls))
        return valid_perms[0] / total_perms
                

                
                
                


class Solution:
    # Brute force: check all permutations
    # O(n! / (ball_count! ^ k)) time, O(n) space 
    def getProbability(self, balls: List[int]) -> float:
        balls_flattened = []
        for i, count in enumerate(balls):
            balls_flattened.extend([i] * count)
        
        def has_same_distinct_color(perm):
            n = len(perm)
            return len(set(perm[: n // 2])) == len(set(perm[n // 2 :]))
        
        total = [0]
        same_distinct_color = [0]
        def get_perm(cur, balls):
            if not balls:
                total[0] += 1
                same_distinct_color[0] += has_same_distinct_color(cur)
                return
            for i in range(len(balls)):
                if i > 0 and balls[i] == balls[i - 1]:
                    continue
                get_perm(cur + [balls[i]], balls[:i] + balls[i + 1 :])
        
        get_perm([], balls_flattened)
        return same_distinct_color[0] / total[0]
    
    # Permutations of combinations
    # O(ball_count ^ k) time (put 0, 1, 2, ..., ball_count balls into box 1, and do it for k colors), O(k) space
    def getProbability(self, balls: List[int]) -> float:
        
        factorial_cache = [1]
        for i in range(1, sum(balls) + 1):
            factorial_cache.append(factorial_cache[-1] * i)
                
        def get_perm_count(arr):
            total = factorial_cache[sum(arr)]
            for a in arr:
                total //= factorial_cache[a]
            return total
        
        total_perms = get_perm_count(balls)
        valid_perms = [0]
        
        def find_valid_split(n, start, distinct1, group1, distinct2, group2):
            if n == 0:
                if distinct1 == distinct2:
                    valid_perms[0] += get_perm_count(group1) * get_perm_count(group2)
                return
            
            for i in range(start, len(group1)):
                if group1[i] == 0:
                    continue
                
                new_num1 = group1[i] - 1
                new_distinct1 = distinct1 if new_num1 > 0 else distinct1 - 1
                new_num2 = group2[i] + 1
                new_distinct2 = distinct2 if new_num2 > 1 else distinct2 + 1
                if new_distinct1 < new_distinct2:
                    continue
                    
                new_group1 = group1[:i] + [new_num1] + group1[i + 1 :]
                new_group2 = group2[:i] + [new_num2] + group2[i + 1 :]
                find_valid_split(n - 1, i, new_distinct1, new_group1, new_distinct2, new_group2)
        
        find_valid_split(sum(balls) // 2, 0, len(balls), balls, 0, [0] * len(balls))
        return valid_perms[0] / total_perms
                

                
                
                


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        def calc(d):
            n = len(d)
            s = sum(d.values())
            result = math.factorial(s)
            for k, v in list(d.items()):
                result /= math.factorial(v)
            return result
        
        def choose(i, k, d1, d2):
            if k == 0 and i <= n:
                for j in range(i, n):
                    d2[j] = balls[j]
                t = calc(d1) * calc(d2)
                e = t if len(d1) == len(d2) else 0
                return t, e 
            if k < 0 or i == n:
                return 0, 0
            t, e = 0, 0
            for j in range(balls[i] + 1):
                if j > 0:
                    d1[i] = j
                if balls[i] - j > 0:
                    d2[i] = balls[i] - j
                else:
                    d2.pop(i)
                a, b = choose(i + 1, k - j, d1, d2)
                t += a
                e += b
            if i in d1:
                d1.pop(i)
            if i in d2:
                d2.pop(i)
            return t, e
        
        n = len(balls)
        k = sum(balls) // 2
        t, e = choose(0, k, {}, {})
        # print(t, e)
        return e / t
            


from functools import lru_cache

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.n = sum(balls) // 2
        self.balls = balls
        return self.dfs(0, 0, 0, 0, 0)
        
    def com(self, n, m):
        ans = 1
        for i in range(n-m+1, n+1):
            ans *= i
        for i in range(1, m+1):
            ans //= i
        return ans
        
    @lru_cache(None)
    def dfs(self, left, right, i, ul, ur):
        if i == len(self.balls):
            return float(ul == ur)
        p = 0
        for l in range(self.balls[i]+1):
            r = self.balls[i] - l
            if left+l > self.n or r+right > self.n:
                continue
            p += self.com(self.n-left, l) * self.com(self.n-right, r) / self.com(2*self.n-left-right, self.balls[i]) * self.dfs(left+l, right+r, i+1, ul+(l>0), ur+(r>0))
        return p

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        M = len(balls)
        N = sum(balls)
        F = [math.factorial(n) for n in range(N // 2 + 1)]
        # every box has at least N // 2 distinct colors, and has at most N distinct colors
        
        s1 = [0] * M
        s2 = [0] * M
        
        def find(i):
            if i == M:
                if sum(s1) == sum(s2) and len([n for n in s1 if n]) == len([n for n in s2 if n]):
                    # print(s1, s2)
                    base1 = F[N // 2]
                    for n in s1:
                        base1 //= F[n]
                    base2 = F[N // 2]
                    for n in s2:
                        base2 //= F[n]
                    self.ans += base1 * base2
                return
            
            for n in range(balls[i]+1):
                s1[i] = n
                s2[i] = balls[i] - n
                find(i+1)
                
        self.ans = 0
        find(0)
        
        base = math.factorial(N)
        for n in balls:
            base //= math.factorial(n)
        
        return self.ans / base

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        M = len(balls)
        N = sum(balls)
        F = [math.factorial(n) for n in range(N // 2 + 1)]
        
        s1 = [0] * M
        s2 = [0] * M
        
        def find(i):
            if i == M:
                if sum(s1) == sum(s2) and len([n for n in s1 if n]) == len([n for n in s2 if n]):
                    base1 = F[N // 2] // math.prod(F[n] for n in s1)
                    base2 = F[N // 2] // math.prod(F[n] for n in s2)
                    return base1 * base2
                return 0
            
            s = 0
            for n in range(balls[i]+1):
                s1[i] = n
                s2[i] = balls[i] - n
                s += find(i+1)
            return s
                
        base = math.factorial(N) // math.prod(math.factorial(n) for n in balls)
        return find(0) / base

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        from math import factorial as f
        n = len(balls)
        first = [0]*n
        second = [0]*n
        self.ans = 0
        def dfs(i):
            if i == n:
                if sum(first) != sum(second):
                    return 
                if len([x for x in first if x != 0]) != len([x for x in second if x != 0]):
                    return
                
                ret = f(sum(first)) * f(sum(second))
                for num in first:
                    if num != 0:
                        ret /= f(num)
                for num in second:
                    if num != 0:
                        ret /= f(num)
                self.ans += ret
                return
                
                
            else:
                for num in range(0, balls[i]+1):
                    first[i] = num
                    second[i] = balls[i]-num
                    dfs(i+1)
        dfs(0)
        
        total = f(sum(balls))
        for num in balls:
            total /= f(num)
        return self.ans/total
                
        


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.n = len(balls)
        self.mem = {0: 1}
        self.mem2 = {}
        self.balls = balls
        rv = self.dfs(0, [], [])
        #print(self.mem2, self.mem)
        return rv / self.multinomial(balls)
        
        
    def dfs(self, idx, lefts, rights):
        if idx >= self.n:
            if not lefts or not rights:
                return 0
            if len(lefts) != len(rights):
                return 0
            if sum(lefts) != sum(rights):
                return 0
            return self.multinomial(lefts)*self.multinomial(rights)
        
        rv = 0
        for i in range(0, self.balls[idx]+1):
            x1 = i
            x2 = self.balls[idx] - x1
            if x1 == 0:
                rights.append(x2)
                rv += self.dfs(idx+1, lefts, rights)
                rights.pop()
            elif x2 == 0:
                lefts.append(x1)
                rv += self.dfs(idx+1, lefts, rights)
                lefts.pop()
            else:
                lefts.append(x1)
                rights.append(x2)
                rv += self.dfs(idx+1, lefts, rights)
                rights.pop()
                lefts.pop()
        return rv

        
    def multinomial(self, arr):
        if not arr:
            return 0
        arr = arr[:]
        arr.sort()
        key = tuple(arr)
        if key in self.mem2:
            return self.mem2[key]
        
        res = self.frac(sum(arr))
        for x in arr:
            res //= self.frac(x)
        self.mem2[key] = res
        return res

    
    def frac(self, x):
        if x in self.mem:
            return self.mem[x]
        rv =  x * self.frac(x-1)
        self.mem[x] = rv
        return rv

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        k, n = len(balls), sum(balls)
        
        total = 2 * math.comb(n, n//2)
        def shuffle(color, box1, box2):
            if color == k:
                if sum(box1) == sum(box2) and  box1.count(0) == box2.count(0):
                    #print(f'{box1} {box2}')
                    ans = 0
                    for box in [box1, box2]:
                        p = 1
                        for c, num in enumerate(box):
                            p *= math.comb(balls[c], num)
                        ans += p
                    return ans
                else:
                    return 0
            # track all possible
            total_p = 0
            bc = balls[color]
            for b in range(0, bc + 1):
                box1[color], box2[color] = b, bc - b
                total_p += shuffle(color + 1, box1, box2)
                box1[color], box2[color] = 0, 0
            return total_p
                
        p = shuffle(0, [ 0 ] * k, [ 0 ] * k)
        return p / total
                
            
            
                


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        
        
        total = sum(balls)
        def factorial(n):
            if n == 0:
                return 1
            if n < 3:
                return n
            return n * factorial(n-1)
        
        self.match = 0
        self.total = 0
        def helper(p, left1, left2, cnt1, cnt2, per1, per2):
            if left1 == 0 and left2 == 0:
                self.total += per1 * per2
                self.match += per1 * per2 * (cnt1 == cnt2)
            elif left1 >= 0 and left2 >= 0:
                for k in range(balls[p]+1):
                    helper(p+1, left1 - k, left2 - balls[p] + k, cnt1 + (k > 0), cnt2 + (balls[p]-k > 0), per1 / factorial(k), per2/factorial(balls[p]-k))
        
        helper(0, total // 2, total //2, 0, 0, factorial(total//2), factorial(total//2))
        # print(self.match)
        # print(self.total)
        return self.match/self.total
                
        
        
#         Track how many balls are left to fill each box as cnt1 and cnt2.
# Count different colors in each box as col1 and col2; compare in the end.
# The initial/maximum number of permutatons in each box is (n / 2)!
# When selecting m balls of particular color, we reduce the number of permutations by m! if the color is the same, no difference, just like [1, 1 / 2, 3] and [1, 1 / 2, 3]. Even we change the position of the two 1, it makes no difference. However, the order of 2, and 3 matters.
# When both cnt1 and cnt2 are zero, prm1 and prm2 are permutations in each box.
# - Number of permutations = (n / 2)! / (m1! * m2! * ... * mk!).
# - The total number of permutations with two boxes is prm1 * prm2.
        
    
    
#         total = sum(balls)
#         k = len(balls)
        
#         def theSame(added):
#             res = 0
#             for i in range(k):
#                 if added[i] == 0:
#                     res -= 1
#                 elif balls[i] == added[i]:
#                     res += 1
#             return res == 0
        
        
#         def combination(this, pick):
#             pick = min(this-pick, pick)
#             res = 1
#             i = this
#             j = 1
#             while i > pick:
#                 res *= i
#                 res /= j
#                 i -= 1
#                 j += 1
#             return res
            
#         def helper(i, added, cur):
            
#             if cur == total // 2:
               
#                 if theSame(added):
#                     res = 1
#                     for i in range(k):
#                         res *= combination(balls[i], added[i])
#                     return res
#                 return 0
#             if i == k:
#                 return 0
#             if cur > total // 2:
#                 return 0
#             res = 0
#             for t in range(balls[i]+1):
#                 added[i] = t
#                 res += helper(i+1, added, cur+t) 
#             added[i] = 0
#             return res
        
#         added = [0] * k 
#         return helper(0, added, 0) / combination(total, total // 2)
        
        
            
                          
                           
                        
                
                    
        
                
                
        
        
        


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        from scipy.special import comb # help to calculate combination numbers
        
        sm = sum(balls)
        number_of_combinations = comb(sm, sm//2) # 
        
        def number_of_ways_to_pick(n): # there are n balls of color-a, we want to pick some number of them and put them into boxA, and others into boxB
            d = Counter() # key: number of balls put into boxA, value: number of such combinations
            for i in range(n+1):
                d[i] = comb(n,i)
            return d
            
        status = Counter()
        status[(0,0,0,0)] = 1 
        #key: num of balls in boxA, num of balls in boxB, different colors in boxA, different colors in boxB; value: number of such combinations
        for n in balls:
            combs = number_of_ways_to_pick(n)
            new_s = Counter()
            for k in status:
                a,b,ca,cb = k
                for n_a in combs:
                    if n_a == 0:
                        new_s[(a,b+n,ca,cb+1)] += status[k] * combs[n_a]
                    elif n_a == n:
                        new_s[(a+n,b,ca+1,cb)] += status[k] * combs[n_a]
                    else:
                        new_s[(a+n_a, b+n-n_a, ca, cb)] += status[k] * combs[n_a]
            status = new_s
        
        res = 0
        for k in status:
            a,b,ca,cb = k
            if a==b and ca==cb:
                res += status[k]
            
        return res/number_of_combinations


from math import factorial

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        # number of distinct arrangements where some balls are identical
        # fact(sum(balls)) / fact(balls[0]) * fact(balls[1]) * .. * fact(balls[n - 1])

        n = len(balls)
        a = [0] * n
        b = balls[:]

        def perm(xs):
            # result = 1
            # j = 1
            # for i in range(n):
            #     for k in range(1, xs[i] + 1):
            #         result = result * j / k
            #         j += 1

            # return result

            result = factorial(sum(xs))
            for x in xs:
                result = result / factorial(x)
            return result

        t = sum(balls) // 2
        def dfs(a, b, i, sa, sb):
            if sa > t:
                return 0

            if i == n:
                if sa != sb:
                    return 0

                ca = sum([1 for x in a if x > 0])
                cb = sum([1 for y in b if y > 0])
                return perm(a) * perm(b) if ca == cb else 0

            result = 0
            for j in range(b[i] + 1):
                a[i] += j
                b[i] -= j
                result += dfs(a, b, i + 1, sa + j, sb - j)
                a[i] -= j
                b[i] += j

            return result


        splits = dfs(a, b, 0, 0, sum(b))
        return round(splits / perm(balls), 5)




class Solution:
    def getProbability(self, balls: List[int]) -> float:
        firsthalf, secondhalf = [0]*len(balls),[0]*len(balls)
        self.good, self.all = 0,0
        
        @lru_cache(None)
        def fac(n):
            if n==0:
                return 1
            return n*fac(n-1)
        
        def permutation(arr):
            prod = 1
            for v in arr:
                prod*=fac(v)
            return fac(sum(arr))/prod
        def dfs(i):
            if i == len(balls):
                if sum(firsthalf)!=sum(secondhalf):
                    return 
                p1,p2 = permutation(firsthalf),permutation(secondhalf)
                self.all+=p1*p2
                self.good +=p1*p2 if sum(v>0 for v in firsthalf)==sum(v>0 for v in secondhalf) else 0
            else:
                for j in range(balls[i]+1):
                    firsthalf[i],secondhalf[i]=j, balls[i]-j
                    dfs(i+1)
        dfs(0)
        return self.good/self.all

class Solution(object):
    def __init__(self):
        self.fact = [1, 1, 2, 6, 24, 120, 720]
        self.total = 0.0
        self.match = 0.0

    def dfs(self, balls, i=0, n=0, c=0, w=1.0):
        if i == len(balls):
            self.total += w * (n == 0)
            self.match += w * (n == 0) * (c == 0)
            return
        for b1, b2 in zip(range(balls[i] + 1), reversed(range(balls[i] + 1))):
            self.dfs(
                balls,
                i + 1,
                n + b1 - b2,
                c + (b2 == 0) - (b1 == 0),
                w / self.fact[b1] / self.fact[b2])

    def getProbability(self, balls):
        self.dfs(balls)
        return self.match / self.total

from math import factorial

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        # number of distinct arrangements where some balls are identical
        # fact(sum(balls)) / fact(balls[0]) * fact(balls[1]) * .. * fact(balls[n - 1])

        n = len(balls)
        a = [0] * n
        b = balls[:]

        def perm(xs):
            result = 1
            j = 1
            for i in range(n):
                for k in range(1, xs[i] + 1):
                    result = result * j / k
                    j += 1
            return result

        t = sum(balls) // 2
        def dfs(a, b, i, sa, sb):
            if sa > t:
                return 0

            if i == n:
                if sa != sb:
                    return 0

                ca = sum([1 for x in a if x > 0])
                cb = sum([1 for y in b if y > 0])
                return perm(a) * perm(b) if ca == cb else 0

            result = 0
            for j in range(b[i] + 1):
                a[i] += j
                b[i] -= j
                result += dfs(a, b, i + 1, sa + j, sb - j)
                a[i] -= j
                b[i] += j

            return result


        splits = dfs(a, b, 0, 0, sum(b))
        return round(splits / perm(balls), 5)




import math
class Solution:
    def getProbability(self, balls):
        k=len(balls)
        first=[0 for _ in range(k)]
        second = [0 for _ in range(k)]
        
        factorial_memo={}
        self.valid=0
        self.successful=0
        def getFactorial(v):
            if v not in factorial_memo:
                factorial_memo[v]=math.factorial(v)
                
            return factorial_memo[v]
        def getPermutation(lst):
            prod=1
            for i in lst:
                prod*=getFactorial(i)
            return getFactorial(sum(lst))/prod
        #start putting one color into two boxes
        def dfs(i):
            
            if i == k:
                if sum(first)!=sum(second):
                    return
                self.valid+=getPermutation(first)*getPermutation(second)
                if sum([v>0 for v in first]) == sum([v>0 for v in second]):
                    self.successful+=getPermutation(first)*getPermutation(second)
            else:
                for n in range(balls[i]+1):
                    first[i]=n
                    second[i]=balls[i]-n
                    dfs(i+1)
        dfs(0)
        return self.successful/self.valid
        
        

        
        
        
        
        
        
        
        
        
        
        
    
    
    
    


import math
class Solution:
    def getProbability(self, balls):
        k=len(balls)
        first=[0 for _ in range(k)]
        second = [0 for _ in range(k)]
        
        factorial_memo={}
        valid=0
        successful=0
        def getFactorial(v):
            if v not in factorial_memo:
                factorial_memo[v]=math.factorial(v)
                
            return factorial_memo[v]
        def getPermutation(lst):
            sum1=0
            for i in lst:
                sum1+=getFactorial(i)
            return getFactorial(sum(lst))/sum1
        #start putting one color into two boxes
        def dfs(i):
            
            if i == k:
                if sum(first)!=sum(second):
                    return
                valid+=getPermutation(first)*getPermutation(second)
                if sum([v>0 for v in getPermutation(first)]) == sum([v>0 for v in getPermutation(second)]):
                    successful+=getPermutation(first)*getPermutation(second)
            else:
                for n in range(balls[i]+1):
                    first[i]=n
                    second[i]=balls[i]-n
                    dfs(i+1)
                    

        dfs(0)
        return successful/valid
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
    
    
    
    
    
    def getProbability(self, balls: List[int]) -> float:
        firstHalf, secondHalf = [0 for _ in range(len(balls))], [0 for _ in range(len(balls))]
        self.good, self.all = 0, 0

        mem_factorial = {}
        def factorial(v):   # e.g., given v = 3, compute 3! = 3*2*1
            if v not in mem_factorial:
                mem_factorial[v] = math.factorial(v)
            return mem_factorial[v]

        def permutation(arr):  # e.g., given arr=[1,1,2,3],compute the number of all distinct permutations, such as `1123`, `1132`..
            prod = 1
            for v in arr:
                prod *= factorial(v)
            return factorial(sum(arr)) / prod

        def dfs(i):
            if i == len(balls):
                if sum(firstHalf) != sum(secondHalf):
                    return
                p1, p2 = permutation(firstHalf), permutation(secondHalf)
                self.all += p1 * p2
                self.good += p1 * p2 if sum(v > 0 for v in firstHalf) == sum(v > 0 for v in secondHalf) else 0
            else:
                for j in range(balls[i]+1):
                    firstHalf[i], secondHalf[i] = j, balls[i]-j
                    dfs(i+1)
                    firstHalf[i], secondHalf[i] = 0, 0
        dfs(0)
        return self.good / self.all

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        firstHalf, secondHalf = [0 for _ in range(len(balls))], [0 for _ in range(len(balls))]
        self.good, self.all = 0, 0

        mem_factorial = {}
        def factorial(v):   # e.g., given v = 3, compute 3! = 3*2*1
            if v not in mem_factorial:
                mem_factorial[v] = v * factorial(v - 1) if v != 0 else 1
            return mem_factorial[v]

        def permutation(arr):  # e.g., given arr=[1,1,2,3],compute the number of all distinct permutations, such as `1123`, `1132`..
            prod = 1
            for v in arr:
                prod *= factorial(v)
            return factorial(sum(arr)) / prod

        def dfs(i):
            if i == len(balls):
                if sum(firstHalf) != sum(secondHalf):
                    return
                p1, p2 = permutation(firstHalf), permutation(secondHalf)
                self.all += p1 * p2
                self.good += p1 * p2 if sum(v > 0 for v in firstHalf) == sum(v > 0 for v in secondHalf) else 0
            else:
                for j in range(balls[i]+1):
                    firstHalf[i], secondHalf[i] = j, balls[i]-j
                    dfs(i+1)
                    firstHalf[i], secondHalf[i] = 0, 0
        dfs(0)
        return self.good / self.all

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        def calc(d):
            n = len(d)
            s = sum(d.values())
            result = 1
            facs = []
            for k, v in list(d.items()):
                facs.append(math.factorial(v))
            facs.sort()
            for i in range(2, s + 1):
                result *= i
                if facs and result > facs[-1]:
                    f = facs.pop()
                    result /= f
            for f in facs:
                result /= f
            return result
        
        t, e = 0, 0
        def choose(i, k, d1, d2):
            nonlocal t
            nonlocal e
            if k == 0 and i <= n:
                for j in range(i, n):
                    d2[j] = balls[j]
                t_ = calc(d1) * calc(d2)
                t += t_
                e += t_ if len(d1) == len(d2) else 0
                return 
            if k < 0 or i == n:
                return
            for j in range(balls[i] + 1):
                if k - j < 0:
                    break
                if j > 0:
                    d1[i] = j
                if balls[i] - j > 0:
                    d2[i] = balls[i] - j
                else:
                    d2.pop(i)
                choose(i + 1, k - j, d1, d2)
            if i in d1:
                d1.pop(i)
            if i in d2:
                d2.pop(i)
        
        n = len(balls)
        k = sum(balls) // 2
        choose(0, k, {}, {})
        # print(t, e)
        return e / t
            


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        def factorial(k):
            if k <= 1:
                return 1
            return factorial(k-1) * k
        
        def calc(balls):
            bs = [b for b in balls if b > 0]
            ans = factorial(sum(bs))
            for b in bs:
                ans /= factorial(b)
            return ans
            
       
        sols = []
        n = sum(balls)//2
        def generate(sol, s, i):
            nonlocal sols
            if s > n:
                return
            
            if i == len(balls):
                if s == n:
                    sols += [sol]
                return
                
            for j in range(0,balls[i]+1):
                generate(sol + [j], s+j, i+1)
        generate([], 0, 0)
        
        count = 0
        for sol in sols:
            l1 = sol
            l2 = [y-x for x,y in zip(l1,balls)]
            l1 = [num for num in l1 if num > 0]
            l2 = [num for num in l2 if num > 0]
            
            if len(l1) == len(l2):
                count += calc(l1) * calc(l2)
                
        return count / calc(balls)

# Sep 8, 2020
# Copied from
# https://leetcode.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/discuss/661723/Struggling-with-probability-problems-Read-this./561118
# The idea:
# A permutation is valid if the number of colors in box A is the same as box B.
class Solution:
    def getProbability(self, balls: List[int]) -> float:
        firstHalf, secondHalf = [0 for _ in range(len(balls))], [0 for _ in range(len(balls))]

        valid_permutations = 0
        all_permutations = 0

        # e.g., given v = 3, compute 3! = 3*2*1
        mem_factorial = {}

        def factorial(v):
            if v not in mem_factorial:
                mem_factorial[v] = v * factorial(v - 1) if v != 0 else 1
            return mem_factorial[v]

        # e.g., given arr=[1,1,2,3],compute the number of all distinct permutations, such as `1123`, `1132`..
        def permutation(arr):
            prod = 1
            for v in arr:
                prod *= factorial(v)
            return factorial(sum(arr)) / prod

        def dfs(i):
            if i == len(balls):
                if sum(firstHalf) != sum(secondHalf):
                    return
                p1, p2 = permutation(firstHalf), permutation(secondHalf)

                nonlocal valid_permutations, all_permutations
                all_permutations += p1 * p2
                valid_permutations += p1 * p2 if sum(v > 0 for v in firstHalf) == sum(v > 0 for v in secondHalf) else 0
            else:
                for j in range(balls[i] + 1):
                    firstHalf[i], secondHalf[i] = j, balls[i] - j
                    dfs(i + 1)
                firstHalf[i], secondHalf[i] = 0, 0

        dfs(0)
        return valid_permutations / all_permutations

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        def factorial(k):
            if k <= 1:
                return 1
            return factorial(k-1) * k
        
        def calc(balls):
            bs = [b for b in balls if b > 0]
            ans = factorial(sum(bs))
            for b in bs:
                ans /= factorial(b)
            return ans
            
       
        sols = []
        n = sum(balls)//2
        def generate(sol, s, i):
            nonlocal sols
            if s > n:
                return
            
            if i == len(balls):
                if s == n:
                    sols += [sol]
                return
                
            for j in range(0,balls[i]+1):
                generate(sol + [j], s+j, i+1)
        generate([], 0, 0)
        
        count = 0
        memo = {}
        for sol in sols:
            l1 = sol
            l2 = [y-x for x,y in zip(l1,balls)]
            l1 = sorted([num for num in l1 if num > 0])
            l2 = sorted([num for num in l2 if num > 0])
            if len(l1) == len(l2):
                l = tuple(l1 + l2)
                if l not in memo:
                    memo[l] = calc(l1) * calc(l2)
                count += calc(l1) * calc(l2)
                
        return count / calc(balls)

class Solution:
    def getProbability(self, balls: List[int]) -> float:
        first, second = [0 for _ in range(len(balls))], [0 for _ in range(len(balls))]
        
        ret = []
        total = []
        self.good = 0
        self.all = 0
        mem_factorial = {}
        def factorial(v):   # e.g., given v = 3, compute 3! = 3*2*1
            if v not in mem_factorial:
                mem_factorial[v] = v * factorial(v - 1) if v != 0 else 1
            return mem_factorial[v]

        def permutation(arr):  # e.g., given arr=[1,1,2,3],compute the number of all distinct permutations, such as `1123`, `1132`..
            prod = 1
            for v in arr:
                prod *= factorial(v)
            return factorial(sum(arr)) / prod
        
        def dfs(i):
            if i == len(balls):
                if sum(first) != sum(second):
                    return
                p1, p2 = permutation(first), permutation(second)
                self.all += p1 * p2
                if sum(v > 0 for v in first) == sum(v > 0 for v in second):
                    self.good += p1 * p2
                return
            for j in range(balls[i]+1):
                first[i], second[i] = j, balls[i] - j
                dfs(i+1)
                first[i], second[i] = 0, 0
            
        dfs(0)
        return self.good/self.all

        
        
        
        


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        first, second = [0 for _ in range(len(balls))], [0 for _ in range(len(balls))]
        
        ret = []
        total = []
        self.good = 0
        self.all = 0
        mem_factorial = {}
        def factorial(v):   # e.g., given v = 3, compute 3! = 3*2*1
            if v not in mem_factorial:
                mem_factorial[v] = v * factorial(v - 1) if v != 0 else 1
            return mem_factorial[v]

        def permutation(arr):  # e.g., given arr=[1,1,2,3],compute the number of all distinct permutations, such as `1123`, `1132`..
            prod = 1
            for v in arr:
                prod *= factorial(v)
            return factorial(sum(arr)) / prod
        
        def dfs(i):
            
            if i == len(balls):
                if sum(first) != sum(second):
                    return
                #total.append((list(first), list(second)))
                p1, p2 = permutation(first), permutation(second)
                #print(p1)
                #print(p2)
                self.all += p1 * p2
                if sum(v > 0 for v in first) == sum(v > 0 for v in second):
                    self.good += p1 * p2
                return
            for j in range(balls[i]+1):
                first[i], second[i] = j, balls[i] - j
                dfs(i+1)
                first[i], second[i] = 0, 0
            
        dfs(0)
        return self.good/self.all

        
        
        
        


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        total = 0
        valid = 0
        
        @lru_cache(None)
        def getFactor(i):
            ans = 1
            for i in range(2, i + 1):
                ans *= i
            return ans
        
        def getComb(nums):
            a = getFactor(sum(nums.values()))
            duplicate = 1
            for val in nums.values():
                duplicate *= getFactor(val)
            return a // duplicate
            
        
        def dfs(i, a, b):
            nonlocal total
            nonlocal valid
            if i == len(balls):
                if sum(a.values()) != sum(b.values()):
                    return
                p1, p2 = getComb(a), getComb(b)
                # print(a, b)
                # print(p1, p2)
                total += p1 * p2
                
                if len(a) == len(b):
                    valid += p1 * p2
            else:
                for j in range(balls[i] + 1):
                    a[i] = j
                    b[i] = balls[i] - j
                    if a[i] == 0:
                        del a[i]
                    if b[i] == 0:
                        del b[i]
                    dfs(i + 1, a, b)         
                    
        dfs(0, {}, {})
        return valid / total

import functools as ft
import math
import operator


class Solution:
    def getProbability(self, balls: List[int]) -> float:
        self.total = 0
        self.valid = 0
        self.balls = balls
        self.k = len(balls)
        self.n = sum(balls) // 2
        self.update([])
        return self.valid / self.total
    
    @ft.lru_cache(None)
    def combination(self, n: int, p: int) -> int:
        return ft.reduce(operator.mul, range(n, n - p, -1), 1) // math.factorial(p)
    
    def count(self, balls: List[int]) -> int:
        ans = 1
        remaining = self.n
        for ball in balls:
            ans *= self.combination(remaining, ball)
            remaining -= ball
        return ans
    
    def update(self, left_balls: List[int]) -> None:
        if len(left_balls) == self.k:
            if sum(left_balls) != self.n:
                return
            right_balls = [total_cnt - left_cnt for left_cnt, total_cnt in zip(left_balls, self.balls)]
            count = self.count(left_balls) * self.count(right_balls)
            self.total += count
            if sum(left_cnt == 0 for left_cnt in left_balls) == sum(right_cnt == 0 for right_cnt in right_balls):
                self.valid += count
            return
        index = len(left_balls)
        left_total = sum(left_balls)
        if left_total + sum(self.balls[index :]) < self.n:
            return
        if left_total > self.n:
            return
        for cnt in range(self.balls[index] + 1):
            self.update(left_balls + [cnt])