{"problem":{"name":"[USACO24JAN] Merging Cells P","description":{"content":"Bessie 正在玩一个著名的在线游戏，游戏中有许多不同编号和大小的细胞。细胞会被其他细胞吞噬，直到只剩下一个胜利者。 有 $N$（$2\\le N\\le 5000$）个细胞从左到右排成一行，编号为 $1\\ldots N$，初始大小为 $s_1,s_2,\\ldots,s_N$（$1\\le s_i\\le 10^5$）。当存在多个细胞时，均匀地随机选择一对相邻细胞，并根据以下规则合并为一个新的细胞： ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10141"},"statements":[{"statement_type":"Markdown","content":"Bessie 正在玩一个著名的在线游戏，游戏中有许多不同编号和大小的细胞。细胞会被其他细胞吞噬，直到只剩下一个胜利者。\n\n有 $N$（$2\\le N\\le 5000$）个细胞从左到右排成一行，编号为 $1\\ldots N$，初始大小为 $s_1,s_2,\\ldots,s_N$（$1\\le s_i\\le 10^5$）。当存在多个细胞时，均匀地随机选择一对相邻细胞，并根据以下规则合并为一个新的细胞：\n\n如果编号为 $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}$。\n\n对于 $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\n## Input\n\n输入的第一行包含 $N$。\n\n第二行包含 $s_1,s_2,\\ldots,s_N$。 \n\n## Output\n\n对于 $1\\ldots N$ 内的每个 $i$ 输出一行，为输出最终的细胞具有编号 $i$ 的概率模 $10^9+7$ 的余数。 \n\n[samples]\n\n## Background\n\n**注意：本题的内存限制为 512MB，通常限制的两倍。**\n\n## Note\n\n### 样例解释 1\n\n存在两种可能性，其中 $(a,b)\\to c$ 表示编号为 $a$ 和 $b$ 的细胞合并成了一个编号为 $c$ 的新的细胞。\n\n$(1, 2) \\to 2, (2, 3) \\to 2$  \n$(2, 3) \\to 3, (1, 3) \\to 3$\n\n所以有各 $\\frac{1}{2}$ 的概率最终的细胞具有编号 $2$ 或 $3$。\n\n### 样例解释 2\n\n六种可能性如下：\n\n$(1, 2) \\to 1, (1, 3) \\to 1, (1, 4) \\to 1$  \n$(1, 2) \\to 1, (3, 4) \\to 4, (1, 4) \\to 1$  \n$(2, 3) \\to 3, (1, 3) \\to 1, (1, 4) \\to 1$  \n$(2, 3) \\to 3, (3, 4) \\to 3, (1, 3) \\to 3$  \n$(3, 4) \\to 4, (2, 4) \\to 4, (1, 4) \\to 4$  \n$(3, 4) \\to 4, (1, 2) \\to 1, (1, 4) \\to 1$\n\n所以有 $\\frac{2}{3}$ 的概率最终的细胞具有编号 $1$，各 $\\frac{1}{6}$ 的概率最终的细胞具有编号 $3$ 或 $4$。\n\n### 测试点性质\n\n- 测试点 3：$N\\le 8$。\n- 测试点 $4-8$：$N\\le 100$。\n- 测试点 $9-14$：$N\\le 500$。\n- 测试点 $15-22$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10141","tags":["动态规划 DP","USACO","2024","概率论"],"sample_group":[["3\n1 1 1","0\n500000004\n500000004"],["4\n3 1 1 1","666666672\n0\n166666668\n166666668"]],"created_at":"2026-03-03 11:09:25"}}