頁面無法載入？點擊這裡可能會修復。
Placeholder

#6222
子任務

군도 (Archipelago) 2s 1024MB

問題

정올이는 여러 섬들이 연결된 군도에서 휴가를 보내고 있다. 이 군도는 N개의 섬과 M개의 양방향 다리로 구성되어 있으며, 각 다리는 두 개의 섬을 연결한다. 섬은 1번부터 N번까지 번호가 매겨져 있고, 다리들은 N-1개 이상, \frac{3}{2}(N-1)개 이하로 연결된다. 또한, 다리들은 연결된 두 섬을 제외하고는 동일한 두 섬을 다시 연결하지 않으며, 다리가 자기 자신에게 연결되거나 두 개의 섬을 동시에 연결하지 않는다.

정올이는 섬 1번에서 시작하여 여행을 한다. 여행 절차는 다음과 같다:

  1. 만약 현재 섬에서 아직 건너지 않은 다리가 없다면, 휴가를 종료한다.

  2. 그렇지 않으면, 확률 p_i \mod (10^9 + 7)로 휴가를 종료한다.

  3. 그 외의 경우, 아직 건너지 않은 다리들 중 하나를 무작위로 선택하여 건넌다.

각 섬에서 휴가를 종료할 확률을 10^9 + 7로 나눈 나머지로 출력하라.


輸入

첫 번째 줄에 독립적인 테스트 케이스의 개수 T가 주어진다 (1 ≤ T ≤ 10).

각 테스트 케이스마다:

  1. 첫 번째 줄에 섬의 개수 N과 다리의 개수 M이 주어진다 (2 ≤ N ≤ 10^4, N-1 ≤ M ≤ 3/2(N-1)).

  2. 두 번째 줄에 각 섬에서 휴가를 종료할 확률 p_1, p_2, \dots, p_N이 주어진다 (0 ≤ p_i​ < 10^9 + 7).

  3. 그다음 M개의 줄에 다리의 정보가 주어진다. 각 줄은 두 섬 u_i, v_i​를 나타낸다 (1 ≤ u_i​ < v_i​ ≤ N).


輸出

각 테스트 케이스마다 각 섬에서 휴가를 종료할 확률을 한 줄에 출력한다. 확률은 10^9 + 7로 나눈 나머지로 출력한다.


子任務

編號 分數 條件
#115分

N \le 11

#216分

단순 사이클이 없다.

#316分

한 섬이 두 개 이상의 단순 사이클에 포함되지 않는다.

#416分

한 섬이 다섯 개 이상의 단순 사이클에 포함되지 않는다.

#517分

한 섬이 50 개 이상의 단순 사이클에 포함되지 않는다.

#620分

추가 제약 조건 없음


範例 #1

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 2
0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334

첫 번째 테스트 케이스에서, p_3 \equiv \frac{1}{9} \mod (10^9 + 7)이다. 정올이는 3번 섬에서 휴가를 종료할 확률이 \frac{1}{9}이고 (경로: 1 \to 3), 2번 섬에서 휴가를 종료할 확률이 \frac{8}{9}​이다 (경로: 1 \to 3 \to 2).

두 번째 테스트 케이스에서는, p_1 \equiv \frac{1}{2} \mod (10^9 + 7)이다. 정올이는 1번 섬에서 휴가를 종료할 확률이 \frac{1}{2}​, 2번과 3번 섬에서 각각 \frac{1}{6}​의 확률로 종료하며, 4번과 6번 섬에서 각각 \frac{1}{12}​의 확률로 종료한다.


範例 #2

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 5
777777784 222222224 0 0 0
0 0 333333336 0 666666672

첫 번째 테스트 케이스에서, p_1 \equiv p_2 \equiv \frac{1}{3} \pmod{10^9 + 7}이다. 정올이는 1번 섬에서 \frac{7}{9}​ 확률로 휴가를 종료할 수 있다 (경로: 1, 1→2→3→4→5→1, 또는 1 \to 5 \to 4 \to 3 \to 2 \to 1).
또한, 2번 섬에서 \frac{2}{9}​ 확률로 휴가를 종료할 수 있다.

두 번째 테스트 케이스에서, 정올이는 3번 섬에서 \frac{1}{3}​ 확률로 휴가를 종료하고, 5번 섬에서 \frac{2}{3}​ 확률로 휴가를 종료할 수 있다.


範例 #3

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 11
133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18

來源

USACO 2024 January Platinum

需要登入才能撰寫程式碼。