codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1999F.md (2087B)


      1 Source: https://codeforces.com/problemset/problem/1999/F
      2 
      3 F. Expected Median
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Arul has a binary array$^{\text{∗}}$ $a$ of length $n$.
     22 
     23 He will take all subsequences$^{\text{†}}$ of length $k$ ($k$ is odd) of this array and find their median.$^{\text{‡}}$
     24 
     25 What is the sum of all these values?
     26 
     27 As this sum can be very large, output it modulo $10^9 + 7$. In other words, print the remainder of this sum when divided by $10^9 + 7$.
     28 
     29 $^{\text{∗}}$A binary array is an array consisting only of zeros and ones.
     30 
     31 $^{\text{†}}$An array $b$ is a subsequence of an array $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements. Subsequences don't have to be contiguous.
     32 
     33 $^{\text{‡}}$The median of an array of odd length $k$ is the $\frac{k+1}{2}$-th element when sorted.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     38 
     39 The first line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $k$ is odd) — the length of the array and the length of the subsequence, respectively.
     40 
     41 The second line of each test case contains $n$ integers $a_i$ ($0 \leq a_i \leq 1$) — the elements of the array.
     42 
     43 It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, print the sum modulo $10^9 + 7$.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 8
     55 
     56 4 3
     57 
     58 1 0 0 1
     59 
     60 5 1
     61 
     62 1 1 1 1 1
     63 
     64 5 5
     65 
     66 0 1 0 1 0
     67 
     68 6 3
     69 
     70 1 0 1 0 1 1
     71 
     72 4 3
     73 
     74 1 0 1 1
     75 
     76 5 3
     77 
     78 1 0 1 1 0
     79 
     80 2 1
     81 
     82 0 0
     83 
     84 34 17
     85 
     86 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 2
     93 5
     94 0
     95 16
     96 4
     97 7
     98 0
     99 333606206
    100 ```
    101 
    102 Note
    103 
    104 In the first test case, there are four subsequences of $[1,0,0,1]$ with length $k=3$:
    105 
    106 * $[1,0,0]$: median $= 0$.
    107 * $[1,0,1]$: median $= 1$.
    108 * $[1,0,1]$: median $= 1$.
    109 * $[0,0,1]$: median $= 0$.
    110 
    111 The sum of the results is $0+1+1+0=2$.
    112 
    113 In the second test case, all subsequences of length $1$ have median $1$, so the answer is $5$.