Sum of medians of all subsets

Revision en1, by 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?

Tags implementations, combinatorics, binomial coefficients


  Rev. Lang. By When Δ Comment
en2 English bihariforces 2023-04-04 13:32:32 29
en1 English bihariforces 2023-04-04 13:26:35 792 Initial revision (published)