E. 第k大 - 2023 年上海市大学生程序设计竞赛 - 六月赛

仪表盘所有提交榜单题解

单点时限: 1.5 sec

内存限制: 256 MB

有 $n$ 个相互独立随机数生成器，第 $i$ 个生成器按均匀分布随机生成 $[0, a_{i}]$ 内的任意实数。

现在需要求解这 $n$ 随机数中排名第 $k$ 大数的期望值，答案对 $10^{9} + 7$ 取模。

第一行一个整数， $n$

第二行 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$

输出一行， $n$ 个整数，第 $i$ 个表示第 $i$ 大数的期望值对 $10^{9} + 7$ 取模的结果（可以证明该期望值是有理数），用一个空格隔开。

Input

3
4 4 4

Output

3 2 1

Input

3
1 2 3

Output

736111118 888888896 375000003

$n \leq 300$

$1 \leq a_{i} \leq 10^{9}$

样例二的期望值分别是 $53 / 72, 8 / 9, 3 / 8$

NaN

比赛状态发生变化，点 OK 刷新。

OK

2023 年上海市大学生程序设计竞赛 - 六月赛