Merging Cells
다이아몬드 IV의견: 0
*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 \(N\) (\(2\le N\le 5000\)) cells in a row labeled \(1\dots N\) from left to
right, with initial sizes \(s_1,s_2,\dots,s_N\) (\(1\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 \(a\) and current size \(c_a\) is merged with a cell with label
\(b\) and current size \(c_b\), the resulting cell has size \(c_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 \(i\) in the range \(1\dots N\), the probability that the final cell
has label \(i\) can be expressed in the form \(\frac{a_i}{b_i}\) where
\(b_i\not\equiv 0\pmod{10^9+7}\). Output \(a_ib_i^{-1}\pmod{10^9+7}\).
Problem credits: Benjamin Qi
SCORING
- Input 3: \(N\le 8\)
- Inputs 4-8: \(N\le 100\)
- Inputs 9-14: \(N\le 500\)
- Inputs 15-22: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\).
The next line contains \(s_1,s_2,\dots, s_N\).
The probability of the final cell having label \(i\) modulo \(10^9+7\) for each \(i\) in \(1\dots N\) on
separate lines.
3
1 1 10
500000004
500000004There 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.
4
3 1 1 1666666672
0
166666668
166666668The 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.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Platinum
평가 및 의견
Merging Cells
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Merging Cells