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.

Source: leetcode | Difficulty: MEDIUM
Tags: Probability

Combinatorics

Complete search

Dynamic programming

Mathematics

Data structures

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):
		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 = sum(balls)
		k = len(balls)
		total = 0
		valid = 0
		fact = [1] * 50
		for i in range(1, 50):
			fact[i] = fact[i - 1] * i

		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:
				if na != nb or uniquea != uniqueb:
					return 0
				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):
			return math.factorial(n) / math.factorial(m) / math.factorial(n - m)

		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 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

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]
			c_overall = self.combination(spaceA + spaceB, currentBallCount)
			for i in range(max(currentBallCount - spaceB, 0), min(currentBallCount, spaceA) + 1):
				j = currentBallCount - i
				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]))
print(s.getProbability([2, 1, 1]))
print(s.getProbability([1, 2, 1, 2]))
print(s.getProbability([6, 6, 6, 6, 6, 6]))


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):
				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


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


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, {}, {})
		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, {}, {})
		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


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)]
		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]
					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:
		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, [], [])
		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):
					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
			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))
		return self.match / self.total


class Solution:

	def getProbability(self, balls: List[int]) -> float:
		from scipy.special import comb
		sm = sum(balls)
		number_of_combinations = comb(sm, sm // 2)

		def number_of_ways_to_pick(n):
			d = Counter()
			for i in range(n + 1):
				d[i] = comb(n, i)
			return d
		status = Counter()
		status[0, 0, 0, 0] = 1
		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:
		n = len(balls)
		a = [0] * n
		b = balls[:]

		def perm(xs):
			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


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

		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

		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):
			if v not in mem_factorial:
				mem_factorial[v] = math.factorial(v)
			return mem_factorial[v]

		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))
				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):
			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):
			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 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)


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))
				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])