No.1451 Walking to School in Groups
タグ : / 解いたユーザー数 72
作問者 :
shiomusubi496
Problem Statement
$N$ students go to school in groups. When they leave home, all $N$ students are each the leader of a group consisting of only themselves, $1$ person, but groups then merge one after another.
The $i$-th merge is given by $2$ integers $a_i,b_i$, which means that the group to which the $a_i$-th student belongs and the group to which the $b_i$-th student belongs merge. (If the two students are in the same group, nothing happens.)
When $2$ groups merge, they become $1$ group, and the leader of whichever of the $2$ groups had more members takes over as the leader of the new group. (There is always exactly $1$ leader per $1$ group.) If the $2$ groups have the same number of members, the leader of one of the groups, chosen at random, becomes the leader of the new group.
The merges are always performed in ascending order of $i$. (Added at 15:10)
After the $M$ merges have finished, for each $i$-th student ($1\leq i\leq N$), find the probability that the student is a leader, $mod\ 10^9+7$, as described in the Notes.
Note that multiple groups may exist at the end, so the final number of leaders is not necessarily one.
Notes
To output a rational number, first represent it as a fraction $\frac{y}{x}$. Here, $x,y$ are integers, and $x$ must not be divisible by $10^9+7$ (under the constraints of this problem, such a representation is always possible).
Then, output the unique integer $z$ between $0$ and $10^9+6$, inclusive, such that $xz\equiv y(mod\ 10^9+7)$.
Input
$N\ M$ $a_1\ b_1$ $a_2\ b_2$ $a_3\ b_3$ $\vdots$ $a_M\ b_M$
- $1\leq N\leq 10^5$
- $0\leq M\leq 10^5$
- $1\leq a_i < b_i \leq N$
- All input values are integers.
Output
Output over $N$ lines.
On the $i$-th line, output the probability that the $i$-th student is finally a leader, in the format described in the Notes.
Sample
Sample 1
Input
4 3 1 2 3 4 1 3
Output
250000002 250000002 250000002 250000002
The probability that each student is finally a leader is $\frac{1}{4}$ for everyone.
Sample 2
Input
7 5 1 2 3 5 4 7 2 6 3 7
Output
500000004 500000004 250000002 250000002 250000002 0 250000002
Sample 3
Input
30 1 7 25
Output
1 1 1 1 1 1 500000004 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 500000004 1 1 1 1 1
The $7$-th student and the $25$-th student are each finally a leader with probability $\frac{1}{2}$, and every other student is always finally a leader.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。