← 返回题目列表

Codeforces · 1983/E

E. 我爱球

中文机器翻译题面 查看原题

Alice 和 Bob 正在玩游戏。有 $$$n$$$ 球,其中 $$$k$$$ 是特殊的。每个球都有一个与之相关的值。

玩家轮流进行游戏。在每个回合中,玩家随机选择一个球,并将球的值添加到他们的分数中,即游戏开始时的 $$$0$$$。选定的球将从游戏中移除。如果球是特殊的,则在至少还剩下一个球的情况下,由同一位球员进行下一回合。如果选择的球不特殊,则轮到下一个玩家进行。

他们玩这个游戏,直到游戏中没有球为止。爱丽丝先玩。

求游戏结束时双方玩家的预期得分以 $$$10^9+7$$$ 为模。

正式地,令 $$$M = 10^9+7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

输入

有多个测试用例。输入的第一行包含一个整数$$$t$$$,即测试用例的数量($$$1 \le t \le 2 \cdot 10^5$$$)。

每个测试用例描述都换行。测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$,按各自的顺序用空格分隔 ($$$1 \le k \le n \le 4 \cdot 10^5$$$)。

测试用例的第二行包含 $$$n$$$ 整数:$$$v_1, v_2, \ldots, v_n$$$,每个球的值以空格分隔。第一个 $$$k$$$ 球很特殊($$$1 \le v_i \le 10^7$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

在新行中输出每个测试用例的两个整数,Alice 的预期分数和 Bob 的预期分数模 $$$10^9+7$$$。

示例

输入 #1

1
5 2
10 20 5 15 25

输出 #1

45 30

输入 #2

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

输出 #2

732507 0
11216370 0
810642660 210218077
722402997 318336932
349086489 678010430

输入 #3

5
3 3
1095611 8219204 7773462
2 1
8176490 2774103
3 1
9178636 5138057 3367761
12 9
7597698 6843019 2298534 1522386 4969588 1340345 3967362 9152890 6689668 9986080 4745473 7407325
10 5
6986368 2397882 5804127 6980694 3740836 3215836 5195724 3179261 4136769 4544231

输出 #3

17088277 0
6862348 4088245
677038671 340645790
36949997 29570371
725118051 321063684

注意

在第一个测试用例中,游戏结束时 Alice 的预期得分为 $$$45$$$,Bob 的预期得分为 $$$30$$$。