Chọn ĐTQG Phú Thọ 2025

Chọn ĐTQG Phú Thọ 2025

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Tích số

Cho hai số nguyên k và n. Với mỗi số nguyên x từ 1 đến k, hãy đếm số lượng mảng số nguyên a sao cho tất cả các điều kiện sau được thỏa mãn:

• 1 ≤ |a| ≤ n, với |a| là độ dài của mảng a.

• 1 ≤ a_i ≤ k với mọi 1 ≤ i ≤ |a|.

• a₁ · a₂ · ⋯ · a_|a| = x (tức là tích của tất cả các phần tử trong mảng a bằng x).

Lưu ý: hai mảng b và c được coi là khác nhau nếu độ dài của chúng khác nhau, hoặc nếu tồn tại chỉ số 1 ≤ i ≤ |b| (độ dài mảng b) sao cho b_i ≠ c_i.

Kết quả cần được in ra theo modulo 998244353.

Input

• Dòng duy nhất chứa hai số nguyên k và n (1 ≤ k ≤ 10⁵, 1 ≤ n ≤ 9 · 10⁸).

Output

• In ra k số nguyên, các số cách nhau bởi dấu cách trên một dòng - số lượng mảng ứng với x = 1, 2, ⋯, k, theo modulo 998244353.

Scoring

Sample Input 1

2 2

Sample Output 1

2 3

Notes

Với x = 1 có 2 dãy thỏa mãn là:

• [1]

• [1, 1]

Với x = 2 có 3 dãy thỏa mãn là:

• [2]

• [1, 2]

• [2, 1]

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Truy vấn đồ thị

Cho một đồ thị vô hướng liên thông có n đỉnh và m cạnh. Các đỉnh của đồ thị được đánh số từ 1 đến n, các cạnh được đánh số từ 1 đến m. Nhiệm vụ của bạn là trả lời q truy vấn, mỗi truy vấn gồm hai số nguyên l và r. Kết quả của mỗi truy vấn là số nguyên không âm lớn nhất k thỏa mãn điều kiện sau:

• Có ít nhất một cặp số nguyên (a, b) sao cho l ≤ a < b ≤ r, hai đỉnh a và b không thể đi đến nhau chỉ bằng cách sử dụng k cạnh đầu tiên (tức là các cạnh 1, 2, ⋯, k).

Input

• Dòng đầu tiên của mỗi test chứa ba số nguyên n, m, q (2 ≤ n ≤ 10⁵, 1 ≤ m, q ≤ 2 · 10⁵) tương ứng là số lượng đỉnh, cạnh, và số truy vấn.

• Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên u_i, v_i (1 ≤ u_i, v_i ≤ n) - biểu diễn cạnh thứ i nối đỉnh u_i và v_i. Dữ liệu đảm bảo rằng đồ thị luôn liên thông, không có cạnh trùng lặp hoặc vòng tự nối (self-loop).

• Mỗi dòng trong q dòng tiếp theo chứa hai số nguyên l, r (1 ≤ l < r ≤ n) - mô tả một truy vấn.

Output

• In ra q số nguyên trên một dòng (các số cách nhau một dấu cách) là kết quả của các truy vấn.

Scoring

Sample Input 1

2 1 1
1 2
1 2

Sample Output 1

0

Sample Input 2

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

Sample Output 2

2 2 4 4

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Truy vấn OR

Tuệ Minh có một mảng a₁, a₂, ⋯, a_n gồm n số nguyên và hai số nguyên không âm x, y. Cô ấy cần thực hiện m truy vấn thuộc hai loại sau:

• 1 l r c: thực hiện phép gán a_i = c với mọi i thỏa mãn (l ≤ i ≤ r), tức là thay các phần tử từ l đến r bằng giá trị c.

• 2 l r: tìm số lượng cặp (L, R) thỏa mãn l ≤ L ≤ R ≤ r và phép OR bitwise của tất cả các phần tử trong đoạn [L, R] nằm trong đoạn [x, y] (lưu ý rằng x, y là hằng số cố định cho tất cả các truy vấn).

Hãy giúp Tuệ Minh thực hiện tất cả các truy vấn đã cho!

Giải thích về phép OR bitwise: Phép OR bitwise được định nghĩa trên cặp số nguyên không âm. Để tính, ta viết cả hai số ở dạng nhị phân. Kết quả là một số nhị phân mà tại mỗi vị trí bit, nếu có ít nhất một số có bit bằng 1 thì kết quả tại vị trí đó là 1.

Ví dụ: 10₁₀ mathbin{OR} 19₁₀ = 1010₂ mathbin{OR} 10011₂ = 11011₂ = 27.

Input

• Dòng đầu chứa bốn số nguyên n, m, x, y (1 ≤ n, m ≤ 3 · 10⁴; 0 ≤ x ≤ y < 2²⁰) — số phần tử, số truy vấn và hai hằng số x, y.

• Dòng thứ hai chứa n số nguyên a₁, a₂, ⋯, a_n (0 ≤ a_i < 2²⁰).

• m dòng tiếp theo mô tả các truy vấn, có 2 dạng:1 l r c (1 ≤ l ≤ r ≤ n; 0 ≤ c < 2²⁰): a_i = c với (l ≤ i ≤ r).2 l r (1 ≤ l ≤ r ≤ n): tìm số lượng đoạn con [L, R] với l ≤ L ≤ R ≤ r sao cho OR của tất cả các phần tử trong đoạn a_L ⋯ a_R nằm trong đoạn [x, y].

Output

Với mỗi truy vấn loại 2, in ra số lượng đoạn con thỏa mãn điều kiện, mỗi số trên một dòng.

Scoring

Sample Input 1

4 8 7 11
0 3 6 1
2 1 4
2 3 4
1 1 4 7
2 1 4
2 1 3
2 1 1
1 3 4 0
2 1 4

Sample Output 1

5
1
10
6
1
7

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Mơ mộng vô hại

Ở đất nước X, phong trào khởi nghiệp rất được quan tâm, nhiều chính sách tốt được ưu tiên dành cho các công ty khởi nghiệp. Bên cạnh đó, việc nghiên cứu thị trường, sức tiêu thụ, chính sách thuế quan,... để từ đó có những chính sách cần thiết nhằm thực hiện tốt kế hoạch đề ra.

Trong bối cảnh đó, một công ty đang có kế hoạch tái cấu trúc nhằm thúc đẩy hoạt động kinh doanh từ đó tăng doanh số bán hàng. Trước khi áp dụng vào thực tiễn, họ sẽ tổ chức thử nghiệm mô hình công ty trên máy tính để mô phỏng quá trình tái cấu trúc này. Trong mô phỏng, nhân viên sẽ có cơ hội được thăng chức làm người đứng đầu công ty thay vì phải làm việc như một nhân viên bình thường.

Cấu trúc của công ty có thể biểu diễn như một cây có gốc tại đỉnh số 1. Cấp trên trực tiếp của nhân viên v là nhân viên p_v. Năng lực của nhân viên v được định nghĩa bởi s_v, các nhân viên khác nhau sẽ có tham số năng lực khác nhau, năng lực càng cao thì nhân viên càng có ích cho công ty. Tuy nhiên nếu quy trình tuyển dụng không minh bạch, có thể xảy ra trường hợp một nhân viên kém năng lực hơn lại là cấp trên của người có năng lực hơn.

Do tái cơ cấu nên ảnh hưởng trực tiếp đáng kể tới nhân sự công ty, mỗi ngày giám đốc điều hành, người đang ở gốc của hệ thống phân cấp công việc sẽ bị sa thải. Nếu còn nhân viên trong công ty, cấp dưới trực tiếp có năng lực nhất sẽ thay thế vị trí của họ. Sau đó, các cấp dưới khác của cựu giám đốc sẽ trở thành cấp dưới của giám đốc mới.

Mỗi nhân viên v đang tính được cần bao nhiêu ngày để họ trở thành giám đốc điều hành. Nhiều người không muốn chờ đợi lâu như vậy, vì họ chỉ được làm giám đốc trong một ngày. Để đẩy nhanh quá trình, họ sẵn sàng "loại bỏ" một trong những đồng nghiệp của mình. Điều này có thể gây tranh cãi nhưng như trên đã nói, chỉ là mô phỏng trên máy tính để thử nghiệm. Mức độ năng lực của nhân viên bị "loại bỏ" giảm xuống 0, vì không ai muốn tương tác với họ nữa.

Yêu cầu : Bạn cần trả lời q truy vấn, với truy vấn thứ k, nhân viên v_k sẽ đứng đầu công ty sau tối thiểu bao nhiêu ngày nếu họ sẵn sàng "loại bỏ" một nhân viên nào đó?

Tất cả truy vấn để trong tưởng tượng và độc lập và mức độ năng lực thực tế của các nhân viên vẫn không thay đổi cho tất cả truy vấn.

Input

• Dòng đầu chứa hai số nguyên n, q (2 ≤ n ≤ 300,000, 1 ≤ q ≤ n) lần lượt là số nhân viên và số truy vấn.

• Dòng thứ hai chứa n - 1 số nguyên p₂, p₃, p₄, ⋯, p_n (1 ≤ p_i < i) là cấp trên trực tiếp của các nhân viên được đánh số từ 2 đến n.

• Dòng thứ ba chứa n số nguyên s₁, s₂, ⋯, s_n (1 ≤ s_i ≤ n) là mức độ năng lực của các nhân viên. Dữ liệu đảm bảo rằng chúng đều khác nhau.

• Dòng thứ tư chứa q số nguyên v₁, v₂, ⋯, v_q (1 ≤ v_i ≤ n) là các truy vấn thăng chức. Đảm bảo rằng tất cả số v_i đều khác nhau.

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Output

• In ra q số nguyên cách nhau bởi dấu cách là số ngày tối thiểu mà các nhân viên v₁, v₂, ⋯, v_q có thể trở thành giám đốc.

Scoring

Sample Input 1

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

Sample Output 1

1 3 0 2

Notes

Trong test ví dụ, nhân viên thứ năm có thể đứng đầu công ty sau 1 ngày. Để làm điều này, việc "loại bỏ" nhân viên thứ hai. Ở ngày 1, nhân viên thứ năm trở thành người đứng đầu, còn nhân viên thứ hai cùng các cấp dưới thứ ba và thứ tư trở thành cấp dưới của nhân viên thứ năm.

Nhân viên thứ ba có thể đứng đầu công ty sau 3 ngày. Để làm điều này, việc "loại bỏ" nhân viên thứ năm hoặc thứ tư. Nếu nhân viên thứ năm bị loại bỏ, ở ngày 1 nhân viên thứ hai đứng đầu với các cấp dưới thứ ba, thứ tư và thứ năm; ở ngày 2 nhân viên thứ tư đứng đầu với các cấp dưới thứ ba và thứ năm; ở ngày 3 nhân viên thứ ba đứng đầu.

Nhân viên thứ nhất đã là người đứng đầu công ty, nên đáp án cho truy vấn tương ứng là 0.

Nhân viên thứ tư có thể trở thành người đứng đầu công ty sau hai ngày. Chỉ cần "loại bỏ" nhân viên thứ năm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. Vẻ đẹp đất nước

Đất nước X là một quốc gia phát triển, đặc biệt là trong lĩnh vực khoa học công nghệ và logistics. Để tiếp tục phát triển đất nước hơn nữa, một trong những chính sách ưu tiên cần thực hiện ngay đó là xây dựng một mạng lưới đường bộ mới. Giữa một số cặp thành phố có các con đường một chiều, con đường thứ i dẫn từ thành phố u_i đến thành phố v_i có độ dài w_i. Hai thành phố chính của X có số hiệu a và b.

Người dân đất nước X rất yêu tổ quốc của mình, họ thích tính toán mọi đặc trưng trong đó. Một trong những đặc trưng yêu thích của họ là "vẻ đẹp". Họ gọi "vẻ đẹp của một đường đi" là phép XOR theo từng bit của độ dài tất cả các con đường trên đường đi đó. Còn "vẻ đẹp của đất nước" họ gọi là phép XOR theo từng bit của vẻ đẹp của tất cả các đường đi từ thành phố a đến thành phố b. Có thể có vô số đường đi như thế và đường đi này có thể đi qua cùng một thành phố nhiều lần.

Người dân muốn biết vẻ đẹp của đất nước của mình bằng bao nhiêu và yêu cầu bạn tính giá trị này hoặc trả lời cho họ biết là không thể tính được vẻ đẹp của đất nước họ dựa trên các số liệu họ cung cấp.

Phép XOR theo từng bit của một tập hợp các số được gọi là phép XOR theo từng bit của tất cả các số khác 0 trong tập hợp đó. Nếu trong tập hợp có vô số số khác 0, thì không thể tính phép XOR theo từng bit.

Phép XOR theo từng bit (hay phép cộng từng bit modulo 2) là một phép toán nhị phân, kết quả của phép toán tương đương phép XOR logic cho từng cặp bit đứng ở cùng vị trí trong biểu diễn nhị phân của các toán hạng. Nói cách khác, nếu các bit tương ứng của các toán hạng khác nhau, thì bit nhị phân tương ứng của kết quả bằng 1; nếu các bit giống nhau, thì bit nhị phân của kết quả bằng 0.

Ví dụ, nếu x = 109₁₀ = 1101101₂ và y = 41₁₀ = 101001₂, thì phép XOR theo từng bit của chúng bằng x oplus y = 1000100₂ = 68₁₀.

Đường đi trong đồ thị được gọi là một dãy các đỉnh, trong đó bất kỳ hai đỉnh liên tiếp nào đều được nối bằng một cạnh.

Input

• Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 40,000) là số bộ dữ liệu đầu vào. Mỗi bộ dữ liệu có cấu trúc được mô tả như sau:Dòng đầu chứa hai số nguyên n và m (1 ≤ n, m ≤ 200,000) tương ứng là số thành phố và số con đường ở đất nước X.Trong m dòng tiếp theo, mỗi dòng chứa 3 số nguyên u_i, v_i và w_i (1 ≤ u_i, v_i ≤ n, 0 ≤ w_i ≤ 2³⁰ - 1).Dòng cuối chứa hai số nguyên a và b (1 ≤ a, b ≤ n).

• Ký hiệu P_n là tổng n, và P_m là tổng m trên tất cả các bộ dữ liệu đầu vào trong một test. Dữ liệu đảm bảo P_n ≤ 200,000 và P_m ≤ 200,000.

Output

Với mỗi bộ dữ liệu đầu vào, in ra một số nguyên là vẻ đẹp của đất nước X trên một dòng. Nếu không có đáp án, thì in -1.

Scoring

Sample Input 1

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

Sample Output 1

0
7
-1
0

Notes

Trong bộ dữ liệu đầu tiên, trong nước chỉ có một con đường có độ dài 0, do đó vẻ đẹp của bất kỳ đường đi nào đều bằng 0, và khi đó phép XOR theo từng bit của vẻ đẹp của tất cả các đường đi bằng 0.

Trong bộ dữ liệu thứ hai, trong nước có tổng cộng 6 đường đi có thể từ thành phố 1 đến thành phố 3, vẻ đẹp của chúng bằng: 0 oplus 5 = 5, 0 oplus 2 = 2, 1 oplus 5 = 4, 1 oplus 2 = 3 và 3 oplus 5 = 6, 3 oplus 2 = 1. Khi đó vẻ đẹp của đất nước: 5 oplus 2 oplus 4 oplus 3 oplus 6 oplus 1 = 7.

Trong bộ dữ liệu thứ ba, từ thành phố 1 đến thành phố 2 có các đường đi có vẻ đẹp 1, 1 oplus 2 oplus 1 = 2, 1 oplus 2 oplus 1 oplus 2 oplus 1 = 1, 1 oplus 2 oplus 1 oplus 2 oplus 1 oplus 2 oplus 1 = 2, ⋯ Khi đó từ thành phố 1 đến thành phố 2 có vô số đường đi với vẻ đẹp khác không, và do đó không thể tính được đáp án.

Trong bộ dữ liệu thứ tư, từ đỉnh 2 đến đỉnh 3 có vô số đường đi có vẻ đẹp 0, và không có đường đi nào có vẻ đẹp khác không. Khi đó vẻ đẹp cuối cùng của đất nước bằng 0.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. Đếm chuỗi con

Công ty khởi nghiệp DroneX được đầu tư sản xuất hàng loạt các máy bay không người lái (drone) phục vụ nông nghiệp. Sản phẩm của họ trợ giúp cho người nông dân có thể bón phân qua lá cho các cây có độ cao lớn như sầu riêng, hồ tiêu, điều, ... Drone của họ cũng được sử dụng trong việc vận chuyển hàng hóa tới các vùng khó khăn - những nơi mà các phương tiện bình thường khác không thể tiếp cận. Mô hình kinh doanh của họ cũng đặc biệt: sản phẩm của họ không bán, chỉ cho thuê trực tiếp tại các cửa hàng tiện ích. Để kích hoạt drone khởi động, khách hàng phải nhập dãy số gồm m số bí mật, nếu chúng trùng khớp trong hệ thống của công ty, drone sẽ được kích hoạt tự động và sẵn sàng bay.

Mỗi khi có khách đến thuê drone, cửa hàng sẽ cung cấp cho khách hàng một chuỗi kí tự t và một tập hợp n chuỗi s₁, s₂, s₃, ⋯, s_n. Để lấy được m số bí mật, công ty sẽ gửi cho mỗi khách hàng m cặp chỉ số l, r. Nhiệm vụ của khách hàng là với mỗi cặp chỉ số l, r đó, lấy chuỗi con của t từ kí tự thứ l đến ký tự thứ r và đếm số lượng chuỗi con này nếu trùng khớp với chuỗi nào đó từ tập đã cho. Thứ tự các số bí mật tìm được phải trùng với thứ tự của các cặp l, r mà khách hàng nhận được.

Sau khi có kết quả, khách hàng sẽ gửi về cho công ty, nếu trùng khớp, drone đã sẵn sàng khởi động.

Một cách tiếp cận khác: Đếm số cặp vị trí (a, b) sao cho l_i ≤ a ≤ b ≤ r_i và chuỗi con của chuỗi t từ vị trí a đến b khớp với một chuỗi s_j nào đó từ tập hợp đã cho.

Chuỗi con của chuỗi t từ vị trí a đến b là chuỗi được tạo ra bằng cách xóa a-1 ký tự đầu và |t|-b ký tự cuối của t, trong đó |t| là độ dài của chuỗi t.

Input

• Dòng đầu tiên chứa hai số nguyên dương n và m (1 ≤ n, m ≤ 500,000) lần lượt là số lượng chuỗi trong tập hợp mà cửa hàng gửi cho khách hàng và số lượng cặp l, r mà công ty gửi cho khách hàng.

• Dòng thứ hai chứa duy nhất chuỗi t, chỉ bao gồm các chữ cái tiếng Anh viết thường (1 ≤ |t| ≤ 5 · 10⁶).

• n dòng tiếp theo mô tả các chuỗi trong tập hợp. Dòng thứ i chứa duy nhất một chuỗi s_i, bao gồm các chữ cái tiếng Anh viết thường. Gọi S là tổng độ dài của tất cả các chuỗi trong tập hợp. Dữ liệu luôn đảm bảo S ≤ 10⁶, và tất cả các chuỗi s_i là khác nhau.

• m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương l_i và r_i (1 ≤ l_i ≤ r_i ≤ |t|) lần lượt là biên trái và biên phải của chuỗi con lấy ra từ chuỗi t từ cặp l, r thứ i.

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Output

• Một dòng duy nhất ghi dãy số bí mật tìm được để gửi kích hoạt drone, trong đó số thứ i là kết quả của cặp l, r thứ i. Các số cách nhau bởi một dấu cách.

Scoring

Sample Input 1

3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5

Sample Output 1

7 3 5 3 1

Notes

• Cặp l, r đầu tiên yêu cầu đếm số lượng chuỗi con của toàn bộ chuỗi khớp với các chuỗi trong tập hợp.Các chuỗi con khớp với"aba"là [1, 3] và [5, 7].Các chuỗi con khớp với"a"là [1, 1], [3, 3], [5, 5], [7, 7].Chuỗi con khớp với"ac"là [3, 4].

Tổng cộng có 7 chuỗi con của"abacaba"khớp với các chuỗi từ tập hợp.

• Trong cặp l, r thứ hai, chuỗi con từ vị trí 1 đến 3 của chuỗi gốc được lấy, đó là chuỗi"aba". Trong đó, chuỗi"aba"xuất hiện 1 lần, chuỗi"a"xuất hiện 2 lần và chuỗi"ac"không xuất hiện lần nào. Tổng là 3.

• Trong cặp l, r thứ ba, chuỗi con từ vị trí 2 đến 7 của chuỗi gốc được lấy, đó là chuỗi"bacaba". Trong đó, chuỗi"aba"xuất hiện 1 lần, chuỗi"a"xuất hiện 3 lần và chuỗi"ac"xuất hiện 1 lần. Tổng là 5.

• Tương tự cho các cặp l, r còn lại.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.