20552번 - 거리의 기댓값 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 35 | 27 | 21 | 77.778% |
문제
$N$개의 정점으로 이루어진 트리 $T_{N}$를 다음과 같은 방법으로 생성한다.
- $T_{1}$은 1번 정점만으로 이루어진 트리다.
- 2 이상의 $i$에 대해 $T_{i}$는 $T_{i-1}$에 $i$번 정점을 $T_{i-1}$의 정점 중 하나와 간선으로 이어 추가한 트리다. $i$번 정점과 연결된 정점이 $j$번 정점이 될 확률은 $\frac{a_j}{a_1+ \cdots + a_{i-1}}$이다. $i$번 정점과 연결된 정점이 $j$번 정점이라면 그 간선의 길이는 $c_i + c_j$이다.
$Q$개의 쿼리가 주어진다. 각 쿼리로 $u$와 $v$가 주어질 때마다 $T_{N}$에서 $u$번 정점과 $v$번 정점의 거리의 기댓값을 구하여라.
입력
첫 번째 줄에 $N$과 $Q$가 주어진다. $(2 \leq N,Q \leq 300\,000)$
두 번째 줄에 $N-1$개의 정수 $a_1,a_2, \cdots, a_{N-1}$이 공백으로 구분되어 주어진다. $(1 \leq a_i \leq 2\,000)$
세 번째 줄에 $N$개의 정수 $c_1,c_2, \cdots, c_N$이 공백으로 구분되어 주어진다. $(1 \leq c_i \leq 2\,000)$
이후 $Q$개의 줄에 걸쳐 쿼리들이 주어진다. 각 줄에는 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$
출력
$i$번째 쿼리의 답을 $ans_i=\frac{p_i}{q_i}$라 하자. ($p_i$, $q_i$는 서로소인 음이 아닌 정수) $i$번째 줄에는 $p_i \equiv q_i x_i \pmod{10^9+7}$를 만족하는 $0$ 이상 $10^9+7$ 미만의 정수 $x_i$를 출력한다. 이 수는 유일하게 존재함을 증명할 수 있다.
예제 입력 1
5 7 1 1 1 1 1 2 4 8 16 1 3 2 5 4 3 1 5 3 3 4 5 1 2
예제 출력 1
7 666666697 15 666666697 0 333333366 3
예제 입력 2
5 4 17 19 23 29 2 3 5 7 11 1 2 3 4 5 2 3 5
예제 출력 2
5 927495315 106531441 450222593
출처
High School > 경기과학고등학교 > 나는코더다 2020 송년대회 A번
Camp > Petrozavodsk Programming Camp > Winter 2021 > Day 9: Grand Prix of Suwon E번
Contest > Open Cup > 2020/2021 Season > Stage 13: Grand Prix of Suwon E번
- 문제를 검수한 사람: cs71107, dlalswp25, koosaga, sebinkim
- 문제를 만든 사람: moonrabbit2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호