Merging Cells

题目描述

注意：本题内存限制为 512MB，是默认值的两倍。 Bessie 正在玩一款著名的在线游戏，游戏中有许多不同标签和大小的细胞。细胞会被其他细胞吞噬，直到只剩下最后一个获胜者。 有 $N$（$2\le N\le 5000$）个细胞排成一行，从左到右标号为 $1\dots N$，初始大小为 $s_1,s_2,\dots,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}.$ 对每个标签 $i$（$1\dots N$），最终剩下的细胞标签为 $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,\dots, s_N$。

输出格式

对每个 $i$（$1\dots N$），输出最终细胞标签为 $i$ 的概率对 $10^9+7$ 取模的结果，每行一个。

3
1 1 1

0
500000004
500000004

4
3 1 1 1

666666672
0
166666668
166666668

提示

有两种可能，其中 $(a,b)\to c$ 表示标签为 $a$ 和 $b$ 的细胞合并成一个标签为 $c$ 的新细胞。 (1, 2) -> 2, (2, 3) -> 2 (2, 3) -> 3, (1, 3) -> 3 因此最终细胞标签为 2 或 3 的概率均为 $1/2$。 六种可能如下： (1, 2) -> 1, (1, 3) -> 1, (1, 4) -> 1 (1, 2) -> 1, (3, 4) -> 4, (1, 4) -> 1 (2, 3) -> 3, (1, 3) -> 1, (1, 4) -> 1 (2, 3) -> 3, (3, 4) -> 3, (1, 3) -> 3 (3, 4) -> 4, (2, 4) -> 4, (1, 4) -> 4 (3, 4) -> 4, (1, 2) -> 1, (1, 4) -> 1 因此最终细胞标签为 1 的概率为 $2/3$，最终细胞标签为 3 或 4 的概率均为 $1/6$。 评分： 输入 3：$N\le 8$ 输入 4-8：$N\le 100$ 输入 9-14：$N\le 500$ 输入 15-22：无额外限制。 题目贡献：Benjamin Qi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum