레이팅 미적용함수 \(\text{randint}(l,r)\)가 범위 \([l, r]\)에서 독립적이고 균등하게 무작위로 정수를 반환한다고 하자.
베시는 다음 두 단계 과정을 사용하여 \(N\)개의 정점 (\(2 \le N \le 2\cdot10^5\))을 가진 무작위 레이블 트리를 생성한다.
- \(1\)부터 \(N\)까지 레이블이 붙은 정점들로 시작한다. \(2\)부터 \(N\)까지의 각 \(i\)에 대해, 정점 \(i\)와 \(\text{randint}(1, i-1)\) 사이에 간선을 추가한다.
- \(\{1, 2, \ldots, N\}\)의 순열 \(p_1,p_2,\dots,p_N\)을 균등하게 무작위로 선택한다. 모든 정점 \(v\)의 레이블을 \(p_v\)로 다시 붙인다.
이제 농부 존은 최종 트리의 간선 집합을 보고 있으며, 위의 두 단계 과정이 정확히 이 간선 집합을 가진 트리를 만들어 낼 확률을 알고 싶다. 이 확률을 \(10^9+7\)로 나눈 나머지로 구할 수 있는가?
문제 제공: Benjamin Qi
채점 방식
- 입력 2-3: \(N\le 8\)
- 입력 4-9: \(N\le 2000\)
- 입력 10-21: 추가 제약 조건이 없다.
문제 제공: Benjamin Qi
입력은 \(T\) (\(1\le T\le 10\))개의 독립적인 입력으로 구성된다. 각 입력은 다음과 같이 주어진다.
첫째 줄에 \(N\)이 주어진다.
다음 \(N-1\)개의 줄에 공백으로 구분된 두 정수 \(u\)와 \(v\) (\(1\le u, v\le N\))로 트리의 간선이 주어진다. 이 간선들이 트리를 이룸이 보장된다.
모든 테스트에 대한 \(N\)의 합은 \(5\cdot 10^5\)를 넘지 않음이 보장된다.
각 테스트마다 확률을 \(10^9+7\)로 나눈 나머지로 한 줄에 출력한다 (출력할 확률은 정수의 비이므로, \(10^9+7\)을 법으로 하여 이 나눗셈의 결과를 출력해야 한다).
4
2
2 1
3
1 2
2 3
4
1 2
2 3
2 4
4
1 2
2 3
3 41
333333336
83333334
55555556The probabilities are \(1\), \(1/3\), \(1/12\), \(1/18\).
First test: There is only one tree on \(N=2\) vertices, so the probability of
generating it is just \(1\).
Second test: there are three trees on \(N=3\) vertices, and each of them is
equally likely to have been generated by the process above. And
\(1/3\equiv 333333336\pmod{10^9+7}\).
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Gold