USACO 2026 - Kỳ thi 3 - Hạng Vàng

Cho một hoán vị \(p_1,p_2,\dots,p_N\) của \(1\dots N\) (\(1\le N\le 2\cdot 10^5\)), đặt

Một hoán vị được gọi là tốt nếu có thể biến nó thành hoán vị đồng nhất bằng không quá \(f(p)\) phép hoán đổi hai phần tử kề nhau.

Cho một hoán vị, hãy tìm những phép dịch vòng của nó tạo thành hoán vị tốt.

Dữ liệu vào

Dữ liệu vào gồm \(T\) (\(1\le T\le 10^5\)) bộ test độc lập. Mỗi bộ test được mô tả như sau:

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

Dòng thứ hai chứa \(p_1,p_2,\dots,p_N\) (\(1\le p_i\le N\)), được đảm bảo là một hoán vị của \(1\dots N\).

Tổng \(N\) trên tất cả các bộ test không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in hai dòng:

Trên dòng đầu tiên, in số lượng phép dịch vòng tốt \(k\).

Sau đó, in một dòng gồm \(k\) số nguyên \(s\) (\(0\le s<N\)) cách nhau bởi dấu cách theo thứ tự tăng dần, biểu thị rằng \(p\) là hoán vị tốt khi được dịch vòng sang phải \(s\) lần.

Ví dụ

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

0

2
0 1
5
0 1 2 3 4

Phân nhóm

• Input 2: \(N\le 10\).
• Inputs 3-5: \(T\le 10, N\le 2000\).
• Inputs 6-11: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Gold Division — bài gốc tiếng Anh “Good Cyclic Shifts”. Tác giả: Akshaj Arora. https://usaco.org/index.php?page=viewproblem2&cpid=1593

Lưu ý: Giới hạn thời gian của bài này là 3 giây, gấp 1,5 lần mức mặc định.

Cấu trúc trang trại của Farmer John có thể được biểu diễn bằng một đồ thị vô hướng liên thông gồm \(N\) đỉnh và \(M\) cạnh không trọng số (\(2\leq N\leq 2\cdot 10^5, N-1\leq M\leq 2\cdot 10^5\)). Ban đầu, Farmer John ở nhà kho của mình, được biểu diễn bởi trang trại \(1\).

Ban đầu, các trang trại \(s_1,s_2,\ldots,s_K\) có những cánh đồng hoa, còn các trang trại \(d_1,d_2,\ldots,d_L\) là các trang trại đích. FJ gọi một đường đi là đẹp nếu:

• Nó bắt đầu tại trang trại \(1\).
• Nó kết thúc tại một trang trại đích \(x\) nào đó.
• Không tồn tại đường đi nào ngắn hơn bắt đầu tại trang trại \(1\) và kết thúc tại trang trại \(x\).
• FJ ghé thăm tất cả các cánh đồng hoa trên đường đi.

FJ có thể vung đũa thần để làm cho nhiều nhất một trang trại nữa có một cánh đồng hoa (nếu trang trại đó chưa có). Tuy nhiên, FJ không giỏi quyết định cho lắm. Với mỗi trang trại \(f\) được đánh số từ \(2\) đến \(N\), sau khi FJ tạm thời làm cho trang trại \(f\) có một cánh đồng hoa, hãy xác định liệu có tồn tại một đường đi đẹp hay không.

Lưu ý rằng có nhiều bộ test và mỗi bộ test phải được xét độc lập.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\leq T\leq 100\)), số lượng bộ test độc lập.

Dòng đầu tiên của mỗi bộ test chứa \(N,M,K,L\) (\(0\leq K\leq N-1, 1\leq L\leq N-1\)).

Dòng tiếp theo chứa \(s_1,s_2,\ldots,s_K\) (\(2\leq s_i\leq N\) và các \(s_i\) đôi một khác nhau).

Dòng tiếp theo chứa \(d_1,d_2,\ldots,d_L\) (\(2\leq d_i\leq N\) và các \(d_i\) đôi một khác nhau).

\(M\) dòng tiếp theo, mỗi dòng chứa \(u\) và \(v\), biểu thị có một cạnh vô hướng nối trang trại \(u\) và trang trại \(v\). Mọi cạnh được xem là có cùng độ dài. Dữ liệu đảm bảo không có cạnh trùng hoặc khuyên.

Tổng \(N\) và tổng \(M\) trên tất cả các bộ test đều không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in một xâu nhị phân có độ dài \(N-1\). Ký tự thứ \(i\) trong xâu phải là \(1\) nếu câu trả lời cho trang trại thứ \((i+1)\) là đúng.

Ví dụ

1
7 7 0 1

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

111110

1
6 6 0 2

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

11010

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

111
000
1011

Phân nhóm

• Inputs 4-6: \(K=0\) và \(L=1\).
• Inputs 7-9: \(K=0\).
• Inputs 10-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Gold Division — bài gốc tiếng Anh “Picking Flowers”. Tác giả: Chongtian Ma. https://usaco.org/index.php?page=viewproblem2&cpid=1594

Giả sử hàm \(\text{randint}(l,r)\) trả về một số nguyên được chọn độc lập và đồng đều ngẫu nhiên trong đoạn \([l,r]\).

Bessie sinh một cây ngẫu nhiên có nhãn gồm \(N\) đỉnh (\(2\le N\le 2\cdot 10^5\)) bằng quy trình hai bước sau:

1. Bắt đầu với các đỉnh được gán nhãn từ \(1\) đến \(N\). Với mỗi \(i\) từ \(2\) đến \(N\), thêm một cạnh nối đỉnh \(i\) với đỉnh \(\text{randint}(1,i-1)\).
2. Chọn đồng đều ngẫu nhiên một hoán vị \(p_1,p_2,\dots,p_N\) của \(\{1,2,\ldots,N\}\). Gán lại nhãn của mỗi đỉnh \(v\) thành \(p_v\).

Bây giờ, Farmer John quan sát tập cạnh của cây cuối cùng và muốn biết xác suất để quy trình hai bước trên sinh ra một cây có tập cạnh chính xác là tập cạnh này. Bạn có thể xác định xác suất đó theo modulo \(10^9+7\) không?

Dữ liệu vào

Dữ liệu vào gồm \(T\) (\(1\le T\le 10\)) bộ test độc lập. Mỗi bộ test được mô tả như sau:

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

\(N-1\) dòng tiếp theo chứa các cạnh của cây, mỗi cạnh được mô tả bởi hai số nguyên \(u\) và \(v\) cách nhau bởi dấu cách (\(1\le u,v\le N\)). Dữ liệu đảm bảo các cạnh này tạo thành một cây.

Tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in xác suất theo modulo \(10^9+7\) trên một dòng mới (lưu ý rằng xác suất cần in là một tỉ số của hai số nguyên, vì vậy bạn cần in kết quả của phép chia này khi tính theo modulo \(10^9+7\)).

Ví dụ

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

1
333333336
83333334
55555556

Phân nhóm

• Inputs 2-3: \(N\le 8\).
• Inputs 4-9: \(N\le 2000\).
• Inputs 10-21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Gold Division — bài gốc tiếng Anh “Random Tree Generation”. Tác giả: Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1595