USACO 2021 - Tháng 2 - Hạng Bạch Kim

Bessie vừa được tặng một bộ dụng cụ vẽ và muốn sơn hàng rào dài ở một đầu đồng cỏ. Hàng rào gồm \(N\) đoạn liên tiếp, mỗi đoạn dài 1 mét (\(1\le N\le2\cdot10^5\)). Bessie có \(N\) màu khác nhau, được đánh số \(1\) đến \(N\) theo độ đậm tăng dần: \(1\) rất nhạt và \(N\) rất đậm. Vì vậy, màu mong muốn của từng đoạn hàng rào được mô tả bằng một mảng \(N\) số nguyên.

Ban đầu, mọi đoạn hàng rào đều chưa được sơn. Trong một nét cọ, Bessie có thể tô một đoạn liên tiếp bất kỳ bằng một màu duy nhất, miễn là cô không bao giờ sơn màu nhạt hơn lên trên màu đậm hơn; cô chỉ có thể phủ màu đậm lên màu nhạt.

Ví dụ, một đoạn chưa tô có độ dài bốn có thể được sơn như sau:

0000 -> 1110 -> 1122 -> 1332

Không may, Bessie không có thời gian chờ sơn khô nên có thể phải để một số đoạn hàng rào chưa sơn. Cô đang xét \(Q\) đoạn ứng viên (\(1\le Q\le2\cdot10^5\)), mỗi đoạn được mô tả bởi hai số nguyên \((a,b)\) với \(1\le a\le b\le N\), là hai đầu mút của đoạn \(a\ldots b\) cần sơn.

Với mỗi đoạn ứng viên, hãy tính số nét cọ ít nhất để sơn mọi đoạn hàng rào bên trong đúng màu mong muốn, đồng thời giữ mọi đoạn bên ngoài chưa sơn. Bessie không thực sự sơn trong quá trình này, nên đáp án của các ứng viên độc lập với nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa một mảng \(N\) số nguyên, biểu thị màu mong muốn của từng đoạn hàng rào.

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách, mô tả một đoạn ứng viên cần sơn.

Dữ liệu ra

Với mỗi ứng viên trong \(Q\) ứng viên, in đáp án trên một dòng mới.

Phân nhóm

• Các test 1-2 thỏa mãn \(N,Q\le100\).
• Các test 3-5 thỏa mãn \(N,Q\le5000\).
• Trong các test 6-10, mảng đầu vào không chứa số nguyên nào lớn hơn \(10\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

8 4
1 2 2 1 1 2 3 2
4 6
3 6
1 6
5 8

2
3
3
3

Nguồn

USACO 2021 February Contest, Platinum - No Time to Dry: https://usaco.org/index.php?page=viewproblem2&cpid=1116

Tác giả: Andi Qu, Brian Dean và Benjamin Qi.

Bessie có một đồ thị vô hướng liên thông \(G\) với \(N\) đỉnh được đánh số \(1\ldots N\) và \(M\) cạnh (\(2\le N\le10^5\), \(N-1\le M\le\frac{N^2+N}{2}\)). \(G\) có thể chứa khuyên, tức cạnh nối một đỉnh với chính nó, nhưng không có cạnh song song nối cùng một cặp đầu mút.

Với mỗi \(1\le a\le N\) và \(0\le b\), đặt \(f_G(a,b)\) là hàm Boolean bằng đúng nếu tồn tại một đường đi từ đỉnh \(1\) đến đỉnh \(a\) đi qua đúng \(b\) cạnh, và bằng sai nếu không tồn tại. Nếu một cạnh được đi qua nhiều lần, mỗi lần đều được tính vào số cạnh.

Elsie muốn sao chép Bessie. Cụ thể, cô muốn xây dựng một đồ thị vô hướng \(G'\) sao cho \(f_{G'}(a,b)=f_G(a,b)\) với mọi \(a\) và \(b\).

Elsie muốn làm ít việc nhất nên cần xây đồ thị nhỏ nhất có thể. Hãy tính số cạnh nhỏ nhất có thể có trong \(G'\).

Mỗi dữ liệu vào chứa \(T\) bộ test (\(1\le T\le5\cdot10^4\)) cần được giải độc lập. Tổng \(N\) trên mọi bộ test không vượt quá \(10^5\), và tổng \(M\) không vượt quá \(2\cdot10^5\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số bộ test.

Dòng đầu của mỗi bộ test chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\) (\(1\le x\le y\le N\)), biểu thị một cạnh giữa \(x\) và \(y\) trong \(G\).

Các bộ test liên tiếp được ngăn cách bằng dòng trống cho dễ đọc.

Dữ liệu ra

Với mỗi bộ test, in trên một dòng mới số cạnh nhỏ nhất có thể có trong \(G'\).

Phân nhóm

• Mọi bộ test trong input 3 thỏa mãn \(N\le5\).
• Mọi bộ test trong các input 4-5 thỏa mãn \(M=N\).
• Với mọi bộ test trong các input 6-9, nếu không phải \(f_G(x,b)=f_G(y,b)\) với mọi \(b\), thì tồn tại \(b\) sao cho \(f_G(x,b)\) đúng và \(f_G(y,b)\) sai.
• Mọi bộ test trong các input 10-15 thỏa mãn \(N\le10^2\).
• Các bộ test trong các input 16-20 không có ràng buộc bổ sung.

Ví dụ

2

5 5
1 2
2 3
2 5
1 4
4 5

5 5
1 2
2 3
3 4
4 5
1 5

4
5

7

8 10
1 2
1 3
1 4
1 5
2 6
3 7
4 8
5 8
6 7
8 8

10 11
1 2
1 5
1 6
2 3
3 4
4 5
4 10
6 7
7 8
8 9
9 9

13 15
1 2
1 5
1 6
2 3
3 4
4 5
6 7
7 8
7 11
8 9
9 10
10 11
11 12
11 13
12 13

16 18
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
8 9
9 10
9 15
9 16
10 11
11 12
12 13
13 14
14 15
14 16

21 22
1 2
1 9
1 12
2 3
3 4
4 5
5 6
6 7
7 8
7 11
8 9
8 10
12 13
13 14
13 21
14 15
15 16
16 17
17 18
18 19
19 20
20 21

20 26
1 2
1 5
1 6
2 3
3 4
4 5
4 7
6 8
8 9
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 10
10 18
11 18
12 19
13 20
14 20
15 20
16 20
17 20
19 20

24 31
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
6 9
8 10
10 11
10 16
10 17
10 18
10 19
10 20
11 12
12 13
13 14
14 15
15 16
15 17
15 18
15 19
15 20
15 21
15 22
15 23
15 24
21 22
23 24

10
11
15
18
22
26
31

Giải thích ví dụ 1. Trong bộ test đầu tiên, Elsie có thể dựng \(G'\) bằng cách bắt đầu từ \(G\) rồi xóa cạnh \((2,5)\). Cô cũng có thể dựng đồ thị gồm các cạnh sau vì không bị giới hạn ở việc chỉ xóa cạnh khỏi \(G\):

1 2
1 4
4 3
4 5

Elsie chắc chắn không thể dùng ít hơn \(N-1\) cạnh vì \(G'\) cũng phải liên thông.

Giải thích ví dụ 2. Trong mỗi bộ test này, Elsie không thể tạo đồ thị có ít cạnh hơn Bessie.

Nguồn

USACO 2021 February Contest, Platinum - Minimizing Edges: https://usaco.org/index.php?page=viewproblem2&cpid=1117

Tác giả: Benjamin Qi.

Bessie có một đồ thị vô hướng liên thông \(G\) với \(N\) đỉnh được đánh số \(1\ldots N\) và \(M\) cạnh (\(2\le N\le10^2\), \(N-1\le M\le\frac{N^2+N}{2}\)). \(G\) có thể chứa khuyên, tức cạnh nối một đỉnh với chính nó, nhưng không có cạnh song song nối cùng một cặp đầu mút.

Với mỗi \(1\le a\le N\) và \(0\le b\), đặt \(f_G(a,b)\) là hàm Boolean bằng đúng nếu tồn tại một đường đi từ đỉnh \(1\) đến đỉnh \(a\) đi qua đúng \(b\) cạnh, và bằng sai nếu không tồn tại. Nếu một cạnh được đi qua nhiều lần, mỗi lần đều được tính vào số cạnh.

Elsie muốn sao chép Bessie. Cụ thể, cô muốn xây dựng một đồ thị vô hướng \(G'\) sao cho \(f_{G'}(a,b)=f_G(a,b)\) với mọi \(a\) và \(b\).

Hãy đếm số đồ thị \(G'\) phân biệt mà Elsie có thể tạo, lấy modulo \(10^9+7\). Giống \(G\), đồ thị \(G'\) có thể chứa khuyên nhưng không có cạnh song song. Vì vậy, trên tổng số \(N\) đỉnh có nhãn, có \(2^{\frac{N^2+N}{2}}\) đồ thị phân biệt.

Mỗi dữ liệu vào chứa \(T\) bộ test (\(1\le T\le\frac{10^5}{4}\)) cần được giải độc lập. Tổng \(N^2\) trên mọi bộ test không vượt quá \(10^5\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số bộ test.

Dòng đầu của mỗi bộ test chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\) (\(1\le x\le y\le N\)), biểu thị một cạnh giữa \(x\) và \(y\) trong \(G\).

Các bộ test liên tiếp được ngăn cách bằng dòng trống cho dễ đọc.

Dữ liệu ra

Với mỗi bộ test, in trên một dòng mới số đồ thị \(G'\) phân biệt, lấy modulo \(10^9+7\).

Phân nhóm

• Mọi bộ test trong input 3 thỏa mãn \(N\le5\).
• Mọi bộ test trong các input 4-5 thỏa mãn \(M=N-1\).
• Với mọi bộ test trong các input 6-11, nếu không phải \(f_G(x,b)=f_G(y,b)\) với mọi \(b\), thì tồn tại \(b\) sao cho \(f_G(x,b)\) đúng và \(f_G(y,b)\) sai.
• Các bộ test trong các input 12-20 không có ràng buộc bổ sung.

Ví dụ

1

5 4
1 2
2 3
1 4
3 5

3

7

4 6
1 2
2 3
3 4
1 3
2 4
1 4

5 5
1 2
2 3
3 4
4 5
1 5

5 7
1 2
1 3
1 5
2 4
3 3
3 4
4 5

6 6
1 2
2 3
3 4
4 5
5 6
6 6

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22

45
35
11
1
15
371842544
256838540

Giải thích ví dụ 1. Trong bộ test đầu tiên, \(G'\) có thể bằng \(G\) hoặc là một trong hai đồ thị sau:

5 4
1 2
1 4
3 4
3 5

5 5
1 2
2 3
1 4
3 4
3 5

Giải thích ví dụ 2. Đây là một số bộ test lớn hơn. Cần in đáp án modulo \(10^9+7\). Đáp án của bộ test áp chót là \(2^{45}\pmod{10^9+7}\).

Nguồn

USACO 2021 February Contest, Platinum - Counting Graphs: https://usaco.org/index.php?page=viewproblem2&cpid=1118

Tác giả: Benjamin Qi.