USACO 2024 January Contest, Platinum, Island Vacation

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
admin
Dạng bài
Điểm: 1000 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bessie đang tận hưởng chuyến du lịch nghỉ dưỡng của mình ở một đất nước có \(N\) \((2 \leq N \leq 10^4)\) hòn đảo được đánh số từ \(1\) đến \(N\). Những hòn đảo này được nối với nhau bằng \(M\) cây cầu \((N - 1 \leq M \leq 3/2(N-1))\).

Những cây cầu được xây theo một số quy tắc như sau:

  • Giữa hai hòn đảo chỉ có duy nhất 1 cây cầu.
  • Không có cây cầu nào nối từ 1 hòn đảo tới chính nó.
  • Mỗi cây cầu chỉ thuộc tối đa 1 chu trình đơn. Một chu trình gọi là chu trình đơn nếu mỗi cạnh trong chu trình đó chỉ được đi qua đúng 1 lần.

Bessie bắt đầu chuyến đi của mình ở đảo \(1\) và di chuyển qua các đảo theo một lộ trình nhất định. Giả sử cô đang ở đảo \(i\):

  1. Nếu không có cây cầu nào nối với đảo \(i\) mà cô chưa đi qua, cô sẽ lập tức kết thúc chuyến đi.
  2. Ngược lại, cô vẫn có tỉ lệ \(p_i\) \((mod\) \(10^9+7)\) cô sẽ kết thúc sớm chuyến đi của mình
  3. Hoặc, cô chọn một trong những cây cầu chưa đi và đi qua nó.

Với mỗi hòn đảo, hãy cho biết tỉ lệ Bessie kết thúc chuyến đi của mình tại hòn đảo đó.

Input

  • Dòng đầu tiên chứa \(T\) \((1 \leq T \leq 10)\) là số lượng test case. Các test case được ngăn cách bởi một dòng trống.
  • Dòng đầu tiên của mỗi test case chứa \(N\) và \(M\), trong đó \(N\) là số lượng các đảo và \(M\) là số lượng các cây cầu. Dữ liệu đảm bảo tổng số \(N\) trong tất cả các test case không vượt quá \(10^4\).
  • Dòng thứ hai của mỗi test case chứa \(N\) số nguyên \(p_1, p_2, …, p_N\) \((0 \leq p_i < 10^9+7)\).
  • \(M\) dòng tiếp theo, mỗi dòng mô tả một cây cầu. Dòng thứ \(i\) chứa hai số nguyên \(u_i\) và \(v_i\) (\(1 \leq u_i \leq v_i \leq N\)), nghĩa là cây cầu thứ \(i\) kết nối các đảo \(u_i\) và \(v_i\).

Output

  • Gồm \(T\) dòng, mỗi dòng là câu trả lời cho từng test case.

Scoring

  • Subtask 1: \(N, Q \leq 10\)
  • Subtask 2: \(N, Q \leq 500\)
  • Subtask 3: \(N, Q \leq 5000\)
  • Subtask 4: Không có ràng buộc thêm.

Example

Test 1

Input 
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
Output 
0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334
Note

  • Đối với test case đầu tiên, \((p_3 = \frac{1}{9} (mod\) \(10^9 + 7))\). Bessie có xác suất (\(\frac{1}{9}\)) kết thúc tại đảo \(3\) (đi theo đường \(1 \to 3\)) và (\(\frac{8}{9}\)) kết thúc tại đảo \(2\) (đi theo đường \(1 \to 3 \to 2\)).

  • Đối với test case thứ hai, \((p_1 = \frac{1}{2} (mod\) \(10^9+7))\). Bessie có xác suất (\(\frac{1}{2}\)) kết thúc tại đảo \(1\), (\(\frac{1}{6}\)) kết thúc tại mỗi đảo \(2\) hoặc \(3\), và (\(\frac{1}{12}\)) kết thúc tại mỗi đảo \(4\) hoặc \(6\).

Test 2

Input 
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
Output 
777777784 222222224 0 0 0
0 0 333333336 0 666666672
Note

  • Trong trường hợp test case đầu tiên, \((p_1 = p_2 = \frac{1}{3}\ (mod\) \(10^9+7))\). Bessie có xác suất (\(\frac{7}{9}\)) kết thúc ở đảo \(1\) (đi theo một trong các con đường \(1\), \(1 \to 2 \to 3 \to 4 \to 5 \to 1\), hoặc \(1 \to 5 \to 4 \to 3 \to 2 \to 1\)) và (\(\frac{2}{9}\)) kết thúc ở đảo \(2\).

  • Trong trường hợp test case thứ hai, Bessie có xác suất (\(\frac{1}{3}\)) kết thúc ở đảo \(3\), và \((\frac{2}{3})\) kết thúc ở đảo 5.

Test 3

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

Bình luận

Không có bình luận nào.