#PU1381. USACO 2024 January Contest, Platinum — Problem 2. Merging Cells

    ID: 1552 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan24来源:usaco.orgscoring:equal_test_cases线段树分块

USACO 2024 January Contest, Platinum — Problem 2. Merging Cells

USACO 2024 January Contest, Platinum — Problem 2. Merging Cells

题目描述

Note: The memory limit for this problem is 512MB, twice the default. Bessie is having fun playing a famous online game, where there are a bunch of cells of different labels and sizes. Cells get eaten by other cells until only one winner remains. There are NN (2≤N≤50002\le N\le 5000) cells in a row labeled 1…N1\dots N from left to right, with initial sizes s1,s2,…,sNs_1,s_2,\dots,s_N (1≤si≤1051\le s_i\le 10^5). While there is more than one cell, a pair of adjacent cells is selected uniformly at random and merged into a single new cell according to the following rule: If a cell with label aa and current size cac_a is merged with a cell with label bb and current size cbc_b, the resulting cell has size ca+cbc_a+c_b and label equal to that of the larger cell, breaking ties by larger label. Formally, the label of the resulting cell is $\begin{cases} a & c_a > c_b \\ b & c_a < c_b \\ \max(a,b) & c_a = c_b \end{cases}.$ For each label ii in the range 1…N1\dots N, the probability that the final cell has label ii can be expressed in the form aibi\frac{a_i}{b_i} where bi≢0(mod109+7)b_i\not\equiv 0\pmod{10^9+7}. Output aibi−1(mod109+7)a_ib_i^{-1}\pmod{10^9+7}.

输入格式

The first line contains NN. The next line contains s1,s2,…,sNs_1,s_2,\dots, s_N.

输出格式

The probability of the final cell having label ii modulo 109+710^9+7 for each ii in 1…N1\dots N on separate lines.

数据范围

(见题面原文)

样例

样例 1

3
1 1 1
0
500000004
500000004
There are two possibilities, where $(a,b)\to c$ means that the cells with labels
$a$ and $b$ merge into a new cell with label $c$.
(1, 2) -> 2, (2, 3) -> 2
(2, 3) -> 3, (1, 3) -> 3
So with probability $1/2$ the final cell has label 2 or 3.

样例 2

4
3 1 1 1
666666672
0
166666668
166666668
The six possibilities are as follows:
(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
So with probability $2/3$ the final cell has label 1, and with probability $1/6$
the final cell has label 3 or 4.