| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 96 | 47 | 34 | 53.968% |
깊이가 $H$인 완전 $K$-진 트리에서 임의의 서로 다른 두 정점 사이의 거리의 기댓값을 계산하라.
완전 $K$-진 트리란, 리프 정점(자식이 없는 정점)을 제외한 모든 정점이 $K$개의 자식 정점을 지닌 트리를 의미한다.
완전 $K$-진 트리에서 모든 리프 정점은 항상 루트 정점으로부터 $H - 1$만큼 떨어져 있다.
각각의 정점은 균등한 확률으로 선택된다.
첫 번째 줄에 정수 $Q$가 주어진다.
두 번째 줄부터 $Q$개의 줄 중 $i$번째 줄에 두 정수 $H_i$와 $K_i$가 공백으로 구분되어 주어진다.
$Q$개의 줄에 걸쳐, $i$번째 줄에 깊이가 $H_i$인 $K_i$-진 트리에서 임의의 두 정점 사이의 거리의 기댓값을 출력하여라. 단, 서로 다른 두 정점을 고를 수 없는 경우에는 0ドル$을 출력하여라.
기댓값은 항상 유리수임을 보일 수 있다. 이 유리수를 기약분수 형태로 나타내면 $\frac{a}{b}$라 할 때, $(a \cdot b^{-1}) \bmod 1,000円,000円,007円$을 출력하여라. 이때 1ドル,000円,000円,007円$은 소수이다.
어떤 소수 $p$와 정수 $a,b$에 대해 $\gcd(b,p)=1$이라면, $(a \cdot b^{-1}) \bmod p$는 $bx \equiv a\pmod{p}$를 만족하는 가장 작은 음이 아닌 정수 $x$로 정의된다.
$b$가 1ドル,000円,000円,007円$의 배수인 테스트 케이스는 입력으로 주어지지 않는다.
3 2 3 4 5 6 7
500000005 110835407 452708333
첫 번째 예제에서 거리의 기댓값은 $\cfrac{3}{2}$이다.
두 번째 예제에서 거리의 기댓값은 $\cfrac{6125}{1209}$이다.
School > 경기과학고등학교 > 나는코더다 2024 송년대회 K번