A6150. 「USACO 2024.1 Platinum」Merging Cells
编程题
省选/NOI-
知识点
题目描述
**题目来自 [USACO 2024 January Contest, Platinum](http://usaco.org/index.php?page=jan24results) Problem 2. [Merging Cells](http://usaco.org/index.php?page=viewproblem2&cpid=1381)**
Bessie 正在玩一个著名的在线游戏，游戏中有许多不同编号和大小的细胞。细胞会被其他细胞吞噬，直到只剩下一个胜利者。
有 $N$（$2\le N\le 5000$）个细胞从左到右排成一行，编号为 $1\ldots N$，初始大小为 $s_1,s_2,\ldots ,s_N$（$1\le s_i\le 10^5$）。当存在多个细胞时，均匀地随机选择一对相邻细胞，并根据以下规则合并为一个新的细胞：
如果编号为 $a$ 且当前大小为 $c_a$ 的细胞与编号为 $b$ 且当前大小为 $c_b$ 的细胞合并，则合并成的细胞的大小为 $c_a+c_b$，且编号等于较大细胞的编号，并列时则为编号较大的细胞的编号。形式化地说，合并成的细胞的编号为 $\begin{cases}a & c_a>c_b\\b & c_a<c_b\\\max(a,b) & c_a=c_b\end{cases}$。
对于 $1\ldots N$ 范围内的每个编号 $i$，最终的细胞具有编号 $i$ 的概率可以以 $\frac{a_i}{b_i}$ 的形式表示，其中 $b_i\not\equiv 0 \pmod{10^9+7}$。输出 $a_ib_i^{-1}\pmod{10^9+7}$。
Bessie 正在玩一个著名的在线游戏，游戏中有许多不同编号和大小的细胞。细胞会被其他细胞吞噬，直到只剩下一个胜利者。
有 $N$（$2\le N\le 5000$）个细胞从左到右排成一行，编号为 $1\ldots N$，初始大小为 $s_1,s_2,\ldots ,s_N$（$1\le s_i\le 10^5$）。当存在多个细胞时，均匀地随机选择一对相邻细胞，并根据以下规则合并为一个新的细胞：
如果编号为 $a$ 且当前大小为 $c_a$ 的细胞与编号为 $b$ 且当前大小为 $c_b$ 的细胞合并，则合并成的细胞的大小为 $c_a+c_b$，且编号等于较大细胞的编号，并列时则为编号较大的细胞的编号。形式化地说，合并成的细胞的编号为 $\begin{cases}a & c_a>c_b\\b & c_a<c_b\\\max(a,b) & c_a=c_b\end{cases}$。
对于 $1\ldots N$ 范围内的每个编号 $i$，最终的细胞具有编号 $i$ 的概率可以以 $\frac{a_i}{b_i}$ 的形式表示，其中 $b_i\not\equiv 0 \pmod{10^9+7}$。输出 $a_ib_i^{-1}\pmod{10^9+7}$。
输入格式
输入的第一行包含 $N$。
第二行包含 $s_1,s_2,\ldots ,s_N$。
第二行包含 $s_1,s_2,\ldots ,s_N$。
输出格式
对于 $1\ldots N$ 内的每个 $i$ 输出一行，为输出最终的细胞具有编号 $i$ 的概率模 $10^9+7$ 的余数。
输入输出样例
输入 #1
3 1 1 1
输出 #1
0 500000004 500000004
输入 #2
4 3 1 1 1
输出 #2
666666672 0 166666668 166666668
说明/提示
- 测试点 3：$N\le 8$。
- 测试点 4-8：$N\le 100$。
- 测试点 9-14：$N\le 500$。
- 测试点 15-22：没有额外限制。
供题：Benjamin Qi
- 测试点 4-8：$N\le 100$。
- 测试点 9-14：$N\le 500$。
- 测试点 15-22：没有额外限制。
供题：Benjamin Qi