레이팅 미적용수학 지식을 늘리기 위해 베시는 그래프 이론 강의를 듣고 있는데, 다음 문제에서 막혀 버렸다. 베시를 도와주자!
정점에 \(1\dots N\)의 번호가, 간선에 \(1\dots M\)의 번호가 붙은 연결된 무방향 그래프가 주어진다 (\(2\le N\le 2\cdot 10^5\), \(N-1\le M\le 4\cdot 10^5\)). 그래프의 각 정점 \(v\)에 대해 다음 과정을 수행한다.
- \(S=\{v\}\), \(h=0\)으로 둔다.
- \(|S|
- \(e\)의 끝점 중 \(S\)에 속하지 않은 정점을 \(S\)에 추가한다.
- \(h=10h+e\)로 갱신한다.
그리고 \(h\pmod{10^9+7}\)을 반환한다. 이 과정의 모든 반환값을 구하여라.
출제: Benjamin Qi
배점
- 입력 4: \(N,M\le 2000\)
- 입력 5-6: \(N\le 2000\)
- 입력 7-10: \(N\le 10000\)
- 입력 11-14: 모든 \(e\)에 대해 \(a_e+1=b_e\)
- 입력 15-23: 추가 제약 없음.
출제: Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(M\)개의 줄 중 \(e\)번째 줄에 \(e\)번째 간선의 두 끝점 \((a_e,b_e)\)가 주어진다 (\(1\le a_e
\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 정점 \(i\)에서 시작한 과정의 반환값을 출력한다.
3 2
1 2
2 312
12
215 6
1 2
3 4
2 4
2 3
2 5
1 51325
1325
2315
2315
5132Consider starting at \(i=3\). First, we choose edge \(2\), after which
\(S = \{3, 4\}\) and \(h = 2\). Second, we choose edge \(3\), after which
\(S = \{2, 3, 4\}\) and \(h = 23\). Third, we choose edge \(1\), after which
\(S = \{1, 2, 3, 4\}\) and \(h = 231\). Finally, we choose edge \(5\), after which
\(S = \{1, 2, 3, 4, 5\}\) and \(h = 2315\). The answer for \(i=3\) is therefore
\(2315\).
15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081Make sure to output the answers modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Platinum