| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 106 | 49 | 43 | 53.750% |
월간 향유회의 $N$명의 운영진들은 각자의 공을 가지고 게임을 하려고 한다. 각 운영진에게는 1ドル$부터 $N$까지의 번호가 차례대로 부여되어 있으며, $i$번 운영진은 $A_i$개의 공을 가지고 있다.
게임은 총 $Q$개의 라운드로 진행되며, 각 라운드에는 $l_i$번부터 $r_i$번까지의 운영진이 참가한다. 한 라운드에 참가한 운영진들은 각자의 공을 모두 속이 보이지 않는 한 상자에 넣고 섞는다. 그리고 상자가 빌 때까지 상자에서 공을 무작위로 하나씩 뽑는데, 이때 $i$번 운영진의 공이 연속으로 뽑힐 때마다 $i$번 운영진이 1ドル$점을 얻는다. 각 라운드가 끝나면 해당 라운드에 참가한 운영진들은 자신의 공을 모두 회수한다.
모든 라운드가 끝난 후, 각 운영진의 점수의 기댓값을 구하여라.
첫째 줄에 운영진의 수 $N$과 라운드의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N, Q \leq 200,000円)$
둘째 줄에 각 운영진의 공의 수 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 5,000円)$
다음 $Q$개의 줄에 각 라운드에 참가할 운영진 번호의 범위 $l_i,ドル $r_i$가 공백으로 구분되어 주어진다. $(1 \leq l_i \leq r_i \leq N)$
$E_1,ドル $E_2,ドル $\cdots,ドル $E_N$을 한 줄에 공백으로 구분하여 출력한다. 이때, $E_i$는 $i$번 운영진의 점수의 기댓값이 기약분수 $\displaystyle \frac{p_i}{q_i}$일 때, $p_i \equiv q_iE_i \pmod {10^9+7}$을 만족하는 0ドル$ 이상 10ドル^9+7$ 미만의 정수이다. 주어진 조건 내에서 $E_i$가 항상 유일함을 증명할 수 있다.
3 2 2 2 3 1 2 2 3
500000004 300000003 400000004
첫 번째 라운드가 끝난 뒤 각 운영진이 받은 점수의 기댓값은 $\left[\frac{1}{2}, \frac{1}{2}, 0\right]$이다.
두 번째 라운드가 끝난 뒤 각 운영진이 받은 점수의 기댓값은 $\left[\frac{1}{2}, \frac{9}{10}, \frac{6}{5}\right]$이다.
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 11. B번