Sum of medians of all subsets

Revision en2, by bihariforces, 2023-04-04 13:32:32

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$, median is the middle element for odd-length subsets when sorted.

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?

#### History

Revisions

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