Sum of medians of all subsets

Правка en1, от bihariforces, 2023-04-04 13:26:35

Let's stick to only odd-length subsets for simplicity, given an array of integers, find sum of median of all subsets mod $$$1e9 + 7$$$, which is the middle element for odd-length subarrays.

First step would obviously be sorting but then to count number of subsets whose median is $$$arr[i]$$$ we need to find number of ways to pick equal number of elements from it's left and right, if left has $$$x$$$ elements and right has $$$y$$$ elements, then,

$$$ count(subsets) = \sum_{i=0}^{\min(x,y)} \binom{x}{i} \binom{y}{i} $$$

Finding this for each element would make it $$$O(N^2)$$$, is there a faster method to find the sum of binomial coefficients as shown above efficiently possibly with some precomputation? Or some entirely different approach to solve the original problem?

Теги implementations, combinatorics, binomial coefficients

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский bihariforces 2023-04-04 13:32:32 29
en1 Английский bihariforces 2023-04-04 13:26:35 792 Initial revision (published)