레이팅 미적용베시는 연결된 무향 그래프들의 모음 \(G_1,G_2,\ldots,G_K\)(\(2\le K\le 5\cdot 10^4\))를 가지고 있다. 각 \(1\le i\le K\)에 대해 \(G_i\)는 \(1\ldots N_i\)로 라벨이 붙은 정확히 \(N_i\)개(\(N_i\ge 2\))의 정점과 \(M_i\)개(\(M_i\ge N_i-1\))의 간선을 갖는다. 각 \(G_i\)에는 자기 자신으로 가는 루프가 있을 수 있지만, 같은 정점 쌍 사이의 다중 간선은 없다.
이제 엘시는 \(N_1\cdot N_2\cdots N_K\)개의 정점을 갖는 새로운 무향 그래프 \(G\)를 만든다. 각 정점은 \(1\le j_i\le N_i\)인 \(K\)-튜플 \((j_1,j_2,\ldots,j_K)\)로 라벨이 붙는다. \(G\)에서 두 정점 \((j_1,j_2,\ldots,j_K)\)와 \((k_1,k_2,\ldots,k_K)\)는 모든 \(1\le i\le K\)에 대해 \(j_i\)와 \(k_i\)가 \(G_i\)에서 간선으로 연결되어 있을 때 간선으로 연결된다.
\(G\)에서 같은 연결 요소에 속한 두 정점 사이의 거리를 한 정점에서 다른 정점으로 가는 경로에 포함된 간선 수의 최솟값으로 정의한다. 정점 \((1,1,\ldots,1)\)과 \(G\)에서 그 정점과 같은 연결 요소에 속한 모든 정점 사이의 거리의 합을 \(10^9+7\)로 나눈 나머지를 계산하시오.
문제 제공: Benjamin Qi
배점
- 테스트 케이스 3-4는 \(\prod N_i\le 300\)을 만족한다.
- 테스트 케이스 5-10은 \(\sum N_i\le 300\)을 만족한다.
- 테스트 케이스 11-20에는 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 그래프의 개수 \(K\)가 주어진다.
각 그래프의 설명은 한 줄에 \(N_i\)와 \(M_i\)가 주어지는 것으로 시작하며, 이어서 \(M_i\)개의 간선이 주어진다.
연속한 그래프 사이에는 가독성을 위해 빈 줄이 있다. \(\sum N_i\le 10^5\)이고 \(\sum M_i\le 2\cdot 10^5\)임이 보장된다.
정점 \((1,1,\ldots,1)\)과 그 정점에서 도달할 수 있는 모든 정점 사이의 거리의 합을 \(10^9+7\)로 나눈 나머지를 출력한다.
2
2 1
1 2
4 4
1 2
2 3
3 4
4 14\(G\) contains \(2\cdot 4=8\) vertices, \(4\) of which are not connected to vertex
\((1,1)\). There are \(2\) vertices that are distance \(1\) away from \((1,1)\) and \(1\)
that is distance \(2\) away. So the answer is \(2\cdot 1+1\cdot 2=4\).
3
4 4
1 2
2 3
3 1
3 4
6 5
1 2
2 3
3 4
4 5
5 6
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1706\(G\) contains \(4\cdot 6\cdot 7=168\) vertices, all of which are connected to
vertex \((1,1,1)\). The number of vertices that are distance \(i\) away from
\((1,1,1)\) for each \(i\in [1,7]\) is given by the \(i\)-th element of the following
array:
\([4,23,28,36,40,24,12]\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > January > Platinum