I Love Balls
Contest: Codeforces Round 956 (Div. 2) and ByteRace 2024
Difficulty rating: 2300
Tags: combinatorics, math, probabilities

Alice and Bob are playing a game. There are $$$n$$$ balls, out of which $$$k$$$ are special. Each ball has a value associated with it.

The players play turn by turn. In each turn, the player randomly picks a ball and adds the value of the ball to their score, which is $$$0$$$ at the beginning of the game. The selected ball is removed from the game. If the ball was special, the same player takes the next turn if at least one ball is remaining. If the ball picked was not special, the next player plays their turn.

They play this game until no balls are remaining in the game. Alice plays first.

Find the expected score that both the players have at the end of the game modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input format:
There are multiple test cases. The first line of the input contains an integer $$$t$$$, the number of test cases ($$$1 \le t \le 2 \cdot 10^5$$$).

Each test case description is on a new line. The first line of the test case contains two integers $$$n$$$ and $$$k$$$ in the respective order separated by a space ($$$1 \le k \le n \le 4 \cdot 10^5$$$).

The second line of the test case contains $$$n$$$ integers: $$$v_1, v_2, \ldots, v_n$$$, the value for each ball separated by spaces. The first $$$k$$$ balls are special ($$$1 \le v_i \le 10^7$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
Output two integers per test case in a new line, the expected score of Alice and the expected score of Bob modulo $$$10^9+7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Alice's expected score is $$$45$$$, and Bob's is $$$30$$$ at the end of the game.

Example input:
1
5 2
10 20 5 15 25

Example output:
45 30

Example input:
5
1 1
732507
2 2
5817860 5398510
5 1
2122894 4951549 2750585 7821535 3214167
8 4
1405323 5069867 6883092 6972029 328406 2478975 7628890 9973340
4 2
9662050 3566134 3996473 9872255

Example output:
732507 0
11216370 0
810642660 210218077
722402997 318336932
349086489 678010430

Editorial:
When there are no special balls, Alice and Bob alternately pick balls starting with Alice. This means Alice picks $$${\frac{n+1}{2}}$$$ balls if $$$n$$$ is odd or $$$\frac{n}{2}$$$ if $$$n$$$ is even. The total value of all balls is $$$\sum v_i$$$. On average, Alice's score is $$$\lfloor\frac{n + 1}{2}\rfloor \cdot \frac{\sum v_i}{n}$$$.
With $$$k$$$ special balls, the picking order can be interrupted, allowing the same player to pick again. We need to distribute $$$k$$$ special balls into $$$n - k + 1$$$ possible positions (gaps). The expected number of special balls picked by Alice can be derived as the expected number of gaps encountered by Alice ($$$\lfloor\frac{n - k + 2}{2}\rfloor$$$) times the expected number of special balls per gap($$$\frac{k}{n - k + 1}$$$). The formula is $$$\frac{(\lfloor\frac{n - k + 2}{2} \rfloor) \cdot k}{n - k + 1}$$$.
Expected value without special balls: $$$\lfloor\frac{n + 1}{2}\rfloor \cdot \frac{\sum v_i}{n}$$$.
Expected special balls for Alice: $$$\frac{(\lfloor\frac{n - k}{2}\rfloor + 1) \cdot k}{n - k + 1}$$$.
Expected normal balls for Alice when there are non-zero special balls: $$$\lfloor\frac{n - k + 1}{2}\rfloor$$$
Therefore, expected score of Alice: $$$\frac{(\lfloor\frac{n - k}{2}\rfloor + 1) \cdot k}{n - k + 1} \cdot \frac{\sum_{i \in \{1,2, \cdot \cdot \cdot k\}}{v_i}}{k} + \lfloor\frac{n - k + 1}{2}\rfloor \cdot \frac{\sum_{i \in \{k+1,k+2, \cdot \cdot \cdot n\}}{v_i}}{n - k}$$$
Similarly, expected score of Bob: $$$(k - \frac{(\lfloor\frac{n - k}{2}\rfloor + 1) \cdot k}{n - k + 1}) \cdot \frac{\sum_{i \in \{1,2, \cdot \cdot \cdot k\}}{v_i}}{k} + (n - k - \lfloor \frac{n - k + 1}{2} \rfloor) \cdot \frac{\sum_{i \in \{k+1,k+2, \cdot \cdot \cdot n\}}{v_i}}{n - k}$$$