레이팅 미적용베시는 \(1\dots N\)의 번호가 붙은 \(N\) (\(2\le N\le 10^4\))개의 섬이 \(M\)개의 양방향 다리로 연결된 곳에서 휴가를 보내고 있다. 각 다리는 두 섬을 연결한다 (\(N-1\le M\le 3/2(N-1)\)). 다리들이 연결된 단순 그래프를 이룸이 보장된다 (특히 같은 섬 쌍을 잇는 다리가 두 개 이상 없고, 어떤 섬을 자기 자신과 잇는 다리도 없다).
또한 어떤 다리도 두 개 이상의 단순 사이클 위에 있지 않음이 보장된다. 단순 사이클이란 같은 섬을 반복하지 않는 사이클이다.
베시는 섬 \(1\)에서 출발하여 다음 절차에 따라 여행한다. 현재 섬 \(i\)에 있다고 하면,
- 섬 \(i\)에 인접한 다리 중 아직 건너지 않은 다리가 없으면 휴가를 끝낸다.
- 그렇지 않으면 확률 \(p_i\pmod{10^9+7}\)로 휴가를 끝낸다.
- 그렇지 않으면 섬 \(i\)에 인접한 다리 중 아직 건너지 않은 다리 하나를 균등한 확률로 무작위로 골라 건넌다.
각 섬에 대해, 베시가 그 섬에서 휴가를 끝낼 확률을 \(10^9+7\)로 나눈 나머지로 출력하여라.
출제: Benjamin Qi
배점
- 입력 4-5: \(N\le 11\)
- 입력 6-7: 단순 사이클이 없다.
- 입력 8-11: 어떤 섬도 두 개 이상의 단순 사이클 위에 있지 않다.
- 입력 12-15: 어떤 섬도 \(5\)개보다 많은 단순 사이클 위에 있지 않다.
- 입력 16-19: 어떤 섬도 \(50\)개보다 많은 단순 사이클 위에 있지 않다.
- 입력 20-23: 추가 제약 없음.
출제: Benjamin Qi
첫째 줄에 독립적인 테스트 케이스의 개수 \(T\) (\(1\le T\le 10\))가 주어진다. 연속한 테스트 케이스는 빈 줄로 구분된다.
각 테스트의 첫째 줄에 섬의 개수 \(N\)과 다리의 개수 \(M\)이 주어진다. 모든 테스트 케이스에 대한 \(N\)의 합이 \(10^4\)를 넘지 않음이 보장된다.
각 테스트의 둘째 줄에 \(p_1, p_2,\dots, p_N\) (\(0\le p_i<10^9+7\))이 주어진다.
각 테스트의 다음 \(M\)개의 줄에 다리에 대한 설명이 주어진다. \(i\)번째 줄에는 정수 \(u_i\)와 \(v_i\) (\(1\le u_i
각 테스트 케이스마다, 섬 \(1\)부터 \(N\)까지 각 섬에서 휴가를 끝낼 확률을 \(10^9+7\)로 나눈 나머지로 공백으로 구분하여 한 줄에 출력한다.
2
3 2
0 10 111111112
1 3
2 3
6 5
500000004 0 0 0 0 0
1 5
1 3
4 5
5 6
1 20 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334For the first test case, \(p_3\equiv 1/9 \pmod{10^9+7}\). Bessie has probability
\(1/9\) of ending at \(3\) (taking the path \(1\to 3\)) and \(8/9\) of ending at \(2\)
(taking the path \(1\to 3\to 2\)).
For the second test case, \(p_1\equiv 1/2\pmod{10^9+7}\). Bessie has probability
\(1/2\) of ending at \(1\), \(1/6\) of ending at each of \(2\) or \(3\), and \(1/12\) of
ending at each of \(4\) or \(6\).
2
5 5
333333336 333333336 0 0 0
1 2
2 3
3 4
4 5
1 5
5 5
0 0 0 0 0
1 2
2 3
2 4
1 4
1 5777777784 222222224 0 0 0
0 0 333333336 0 666666672For the first test case, \(p_1\equiv p_2\equiv 1/3\pmod{10^9+7}\). Bessie has
probability \(7/9\) of ending at \(1\) (taking one of the paths \(1\),
\(1\to 2\to 3\to 4\to 5\to 1\), or \(1\to 5\to 4\to 3\to 2\to 1\)) and \(2/9\) of
ending at \(2\).
For the second test case, Bessie has probability \(1/3\) of ending at \(3\), and
\(2/3\) of ending at \(5\).
1
11 13
2 3 4 5 6 7 8 9 10 11 12
1 2
1 3
2 3
2 4
4 5
2 5
4 8
5 9
2 6
6 7
2 7
6 10
5 11133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Platinum