USACO 2024 - Tháng 1 - Hạng Bạch Kim

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

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

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

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

Bessie đang cùng bạn bè chơi một tựa game online nổi tiếng. Mục tiêu của game là điều khiển một tế bào đi hấp thụ những tế bào khác cho đến khi chỉ còn một tế bào duy nhất thống trị bản đồ.

Có tất cả \(N\) (\(2 \leq N \leq 5000\)) tế bào, được đánh dấu từ \(1\) đến \(N\) xếp thành một hàng từ trái sang phải, với kích thước ban đầu của mỗi tế bào là \(s_1, s_2, \ldots, s_N\) (\(1 \leq s_i \leq 10^5\)). Những tế bào ở cạnh nhau sẽ được bắt cặp ngẫu nhiên và phải chiến đấu với nhau. Tế bào có kích thước lớn hơn sẽ chiến thắng và hấp thụ tế bào còn lại và tăng kích thước của bản thân lên một giá trị bằng với kích thước của tế bào kia. Trong trường hợp hòa nhau, người có số thứ tự lớn hơn sẽ được tính là chiến thắng.

Với mỗi người chơi, hãy tìm ra tỉ lệ người chơi đó trở thành tế bào cuối cùng và chiến thắng trò chơi. Tỉ lệ chiến thắng của người đó có thể biểu thị dưới dạng \(\frac{a_i}{b_i}\), trong đó \(b \not\equiv 0 (\text{mod } 10^9 +7)\). Hãy in ra \(a_ib_i^{-1} (\text{mod } 10^9 +7)\).

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng tiếp theo chứa \(N\) giá trị \(s_1, s_2, \ldots, s_N\).

Output

• Gồm \(N\) dòng, dòng thứ \(i\) là tỉ lệ chiến thắng của tế bào thứ \(i\). In ra kết quả theo modulo \(10^9 +7\).

Scoring

• Subtask 1: \(N \leq 8\)
• Subtask 2: \(N \leq 100\)
• Subtask 3: \(N \leq 500\)
• Subtask 4: Không có ràng buộc gì thêm.

Example

3
1 1 1

0
500000004
500000004

4
3 1 1 1

666666672
0
166666668
166666668

Nông trại của nông dân John có tất cả \(N\) (\(2 \leq N \leq 2 \times 10^5\)) con bò, được đánh số từ \(1\) đến \(N\). Những con bò đang đứng hóng gió ở vị trí có tọa độ (\(x_i, y_i\)) trên bản đồ của trang trại mô tả dưới dạng trục hai chiều.

Do những con bò quá lười, nông dân John muốn tổ chức một trò chơi cho chúng. Anh John chia đàn bò thành đội "xanh" và "đỏ" theo những quy tắc sau:

• Không có đội nào không có thành viên.
• Mỗi một con bò thuộc tối đa một đội (có thể là không đội nào)
• Một tấm lưới có độ dài vô tận sẽ được đặt song song với trục tung hoặc trục hoành trên bản đồ trang trại, trên một vị trí không nguyên (ví dụ như \(x = 0.5\))

Nhiệm vụ của bạn là giúp nông dân John chia đàn bò thành hai đội và đặt lưới ở giữa hai đội, biết đàn bò quá lười để di chuyển khỏi vị trí chúng đang ở. Hãy nói cho John biết có tất cả bao nhiêu cách để chọn hai đội sao cho thỏa mãn những điều kiện trên, tính theo modulo \(10^9 +7\).

Input

• Dòng đầu tiên chứa một số nguyên \(N\).
• \(N\) dòng tiếp theo mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(x_i\) và \(y_i\).

Output

• Gồm một số nguyên duy nhất là số cách chọn hai đội xanh và đỏ, modulo \(10^9 + 7\).

Scoring

• Subtask 1: \(N \leq 10\)
• Subtask 2: \(N \leq 200\)
• Subtask 3: \(N \leq 3000\)
• Subtask 4: Không có ràng buộc gì thêm.

Example

2
1 2
2 1

2

3
1 1
2 2
3 3

10

3
1 1
2 3
3 2

12

40
1 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
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40

441563023