레이팅 미적용농부 존의 서커스단 소속 소 \(N\)마리(\(1 \leq N \leq 10^5\))가 다가오는 공연을 준비하고 있다. 공연은 모두 \(1\ldots N\)으로 번호가 매겨진 정점들을 가진 트리 위에서 이루어진다. 공연의 "시작 상태"는 수 \(1 \leq K \leq N\)과, 어떤 두 소도 같은 정점에 있지 않도록 소 \(1\dots K\)를 트리의 정점에 배정하는 방법으로 정의된다.
공연에서 소들은 임의로 많은 횟수의 "이동"을 한다. 한 번의 이동에서는 소 한 마리가 현재 정점에서 비어 있는 인접 정점으로 옮겨 간다. 어떤 이동의 나열을 통해 한 시작 상태에서 다른 시작 상태에 도달할 수 있으면, 두 시작 상태는 동치라고 한다.
각 \(1 \leq K \leq N\)에 대해, 시작 상태의 동치류의 개수, 즉 어느 두 개도 동치가 아니도록 고를 수 있는 시작 상태의 최대 개수를 소들이 구하도록 도와주자. 이 수들은 매우 클 수 있으므로, \(10^9 + 7\)로 나눈 나머지를 출력한다.
문제 제공: Dhruv Rohatgi
배점
- 테스트 케이스 3-4는 \(N\le 8\)을 만족한다.
- 테스트 케이스 5-7은 \(N\le 16\)을 만족한다.
- 테스트 케이스 8-10은 \(N\le 100\)을 만족하며 트리는 "별(star)" 모양이다. 즉, 차수가 2보다 큰 정점이 많아야 하나이다.
- 테스트 케이스 11-15는 \(N\le 100\)을 만족한다.
- 테스트 케이스 16-20은 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 \(N\)이 주어진다.
\(2\le i\le N\)번째 줄 각각에 트리에서 \(a_i\)와 \(b_i\) 사이의 간선을 나타내는 두 정수 \(a_i\)와 \(b_i\)가 주어진다.
각 \(1\le i\le N\)에 대해, 출력의 \(i\)번째 줄에 \(K=i\)일 때의 답을 \(10^9+7\)로 나눈 나머지를 출력한다.
circus.in · 출력을 쓸 파일 circus.out5
1 2
2 3
3 4
3 51
1
3
24
120For \(K=1\) and \(K=2,\) any two states can be transformed into one another.
Now consider \(K=3\), and let \(c_i\) denote the location of cow \(i\). The state
\((c_1,c_2,c_3)=(1,2,3)\) is equivalent to the states \((1,2,5)\) and \((1,3,2).\)
However, it is not equivalent to the state \((2,1,3).\)
8
1 3
2 3
3 4
4 5
5 6
6 7
6 81
1
1
6
30
180
5040
40320riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > US Open > Platinum