Chọn đội tuyển HSG quốc gia Phú Thọ 2025-2026

UBND TỈNH PHÚ THỌ SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỀ THI CHÍNH THỨC

KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA Năm học 2025 - 2026
Môn: Tin học
Thời gian: 180 phút mỗi ngày (không kể thời gian giao đề)
Ngày thi thứ nhất: 18/9/2025 - Ngày thi thứ hai: 19/9/2025

---

Ngày thi thứ nhất (18/9/2025)

	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
Bài 1	Tích số	ANUMBER.*	ANUMBER.INP	ANUMBER.OUT	7,0
Bài 2	Truy vấn đồ thị	BQUERY.*	BQUERY.INP	BQUERY.OUT	7,0
Bài 3	Truy vấn OR	COR.*	COR.INP	COR.OUT	6,0

Dấu * được thay thế bởi PAS hoặc CPP hoặc PY tương ứng với ngôn ngữ lập trình Pascal hoặc C++ hoặc Python.

Bài 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ᵢ ≤ 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ᵢ ≠ cᵢ.

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

Dữ liệu vào

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

Dữ liệu ra

• 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.

Ví dụ:

ANUMBER.INP	ANUMBER.OUT	Giải thích
2 2	2 3	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].

Ràng buộc:

• Subtask 1 (20% số điểm): n = 1;
• Subtask 2 (15% số điểm): n ≤ 10, k ≤ 6;
• Subtask 3 (30% số điểm): n ≤ 10⁵;
• Subtask 4 (35% số điểm): Không có ràng buộc gì thêm.

Bài 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).

Dữ liệu vào:

• 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ᵢ, vᵢ (1 ≤ uᵢ, vᵢ ≤ n) - biểu diễn cạnh thứ i nối đỉnh uᵢ và vᵢ. 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.

Dữ liệu ra:

• 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.

Ví dụ:

BQUERY.INP	BQUERY.OUT
2 1 1 1 2 1 2	0
5 5 4 1 2 1 3 2 4 3 4 3 5 1 4 3 4 2 5 3 5	2 2 4 4

Ràng buộc:

• Subtask 1 (20% số điểm): n, m, q ≤ 10²;
• Subtask 2 (20% số điểm): q = 10;
• Subtask 3 (15% số điểm): mỗi truy vấn r = l + 1;
• Subtask 4 (15% số điểm): m, n ≤ 10³;
• Subtask 5 (30% số điểm): Không có ràng buộc gì thêm.

Bài 3. Truy vấn OR

Tuệ Minh có một mảng a₁, a₂, …, aₙ 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ᵢ = 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₁₀ OR 19₁₀ = 01010₂ OR 10011₂ = 11011₂ = 27.

Dữ liệu vào:

• 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ₙ (0 ≤ aᵢ < 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ᵢ = 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].

Dữ liệu ra:

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.

Ví dụ:

COR.INP	COR.OUT
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	5 1 10 6 1 7

Ngày thi thứ hai (19/9/2025)

Bài	Tiêu đề	File chương trình	File dữ liệu	File kết quả	Điểm
Bài 4	Mơ mộng vô hại	DDREAMING.*	DDREAMING.INP	DDREAMING.OUT	7.0
Bài 5	Vẻ đẹp đất nước	EBEAUTY.*	EBEAUTY.INP	EBEAUTY.OUT	7.0
Bài 6	Đếm chuỗi con	FCOUNT.*	FCOUNT.INP	FCOUNT.OUT	6.0

• Dấu * được thay thế bởi PAS hoặc CPP hoặc PY tương ứng với ngôn ngữ lập trình Pascal hoặc C++ hoặc Python.
• Mỗi bài gồm nhiều subtask, mỗi subtask bao gồm nhiều test, điểm của thí sinh được tính theo từng test.

Bài 4. Mơ mộng vô hại (7.0 điểm)

Ở đấ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ᵥ. Năng lực của nhân viên v được định nghĩa bởi sᵥ, 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 dễ dàng 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ₖ 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 đều 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ả các truy vấn.

Dữ liệu: Vào từ file văn bản DDREAMING.INP:

• 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ₙ (1 ≤ pᵢ < 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ₙ (1 ≤ sᵢ ≤ 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ᵢ ≤ n) là các truy vấn thăng chức. Đảm bảo rằng tất cả số vᵢ đề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.

Kết quả: Ghi ra file văn bản DDREAMING.OUT:

• 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.

Ví dụ:

DDREAMING.INP	DDREAMING.OUT
5 4 1 2 2 1 3 5 1 2 4 5 3 1 4	1 3 0 2

Giải thích:

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. Cấu trúc của công ty sẽ thay đổi như sau:

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ỏ, cấu trúc của công ty sẽ thay đổi như sau:

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.

Chấm điểm:

• Subtask 1 (8% số điểm): pᵢ = 1 hoặc pᵢ = i − 1 với pᵢ = 1 cho không quá 2 số i;
• Subtask 2 (6% số điểm): pᵢ = 1 hoặc pᵢ = i − 1;
• Subtask 3 (8% số điểm): n ≤ 50, q ≤ 50;
• Subtask 4 (13% số điểm): n ≤ 1 000, q ≤ 1 000;
• Subtask 5 (11% số điểm): q ≤ 100;
• Subtask 6 (9% số điểm): pᵢ = ⌊i/2⌋;
• Subtask 7 (11% số điểm): Số cấp trên (tập hợp cấp trên trực tiếp và cấp trên của cấp trên) của một nhân viên bất kỳ không vượt quá 100;
• Subtask 8 (14% số điểm): sᵢ > s_(pᵢ) với mọi i > 1;
• Subtask 9 (20% số điểm): Không có ràng buộc bổ sung.

Bài 5. Vẻ đẹp đất nước (7.0 điểm)

Đấ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ᵢ đến thành phố vᵢ có độ dài wᵢ. 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 ⊕ 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.

Dữ liệu: Vào từ file văn bản EBEAUTY.INP:

• 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ᵢ, vᵢ, và wᵢ (1 ≤ uᵢ, vᵢ ≤ n, 0 ≤ wᵢ ≤ 2³⁰ − 1).
  • Dòng cuối chứa hai số nguyên a và b (1 ≤ a, b ≤ n).
• Ký hiệu Pₙ là tổng n, và Pₘ 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ₙ ≤ 200 000 và Pₘ ≤ 200 000.

Kết quả: Ghi ra file văn bản EBEAUTY.OUT:

• 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.

Ví dụ:

EBEAUTY.INP	EBEAUTY.OUT
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	0 7 -1 0

Giải thích:

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 ⊕ 5 = 5, 0 ⊕ 2 = 2, 1 ⊕ 5 = 4, 1 ⊕ 2 = 3 và 3 ⊕ 5 = 6, 3 ⊕ 2 = 1. Khi đó vẻ đẹp của đất nước: 5 ⊕ 2 ⊕ 4 ⊕ 3 ⊕ 6 ⊕ 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 ⊕ 2 ⊕ 1 = 2, 1 ⊕ 2 ⊕ 1 ⊕ 2 ⊕ 1 = 1, 1 ⊕ 2 ⊕ 1 ⊕ 2 ⊕ 1 ⊕ 2 ⊕ 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.

Chấm điểm:

• Subtask 1 (8% số điểm): n = m, uᵢ = i, vᵢ = i + 1 với i < n, uₙ = n, vₙ = 1;
• Subtask 2 (18% số điểm): wᵢ ≤ 1, uᵢ < vᵢ;
• Subtask 3 (18% số điểm): uᵢ < vᵢ;
• Subtask 4 (20% số điểm): Pₙ ≤ 1 000, Pₘ ≤ 1 000, wᵢ ≤ 2¹⁰ − 1;
• Subtask 5 (18% số điểm): wᵢ ≤ 1;
• Subtask 6 (18% số điểm): Không có ràng buộc bổ sung.

Bài 6. Đếm chuỗi con (6.0 điểm)

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 hoá 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ₙ. Để 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ᵢ ≤ a ≤ b ≤ rᵢ và chuỗi con của chuỗi t từ vị trí a đến b khớp với một chuỗi sⱼ 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.

Dữ liệu: Vào từ file văn bản FCOUNT.INP:

• 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ᵢ, 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ᵢ là khác nhau.
• m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương lᵢ và rᵢ (1 ≤ lᵢ ≤ rᵢ ≤ |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.

Kết quả: Ghi ra file văn bản FCOUNT.OUT:

• 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.

Ví dụ:

FCOUNT.INP	FCOUNT.OUT
3 5 abacaba aba a ac 1 7 1 3 2 7 2 5 4 5	7 3 5 3 1

Giải thích:

• 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.

Chấm điểm:

• Subtask 1 (12% số điểm): n ≤ 100, m ≤ 100, |t| ≤ 100, S ≤ 10 000;
• Subtask 2 (14% số điểm): n ≤ 100, m ≤ 500, |t| ≤ 5 000;
• Subtask 3 (11% số điểm): n ≤ 5 000, |t| ≤ 5 000;
• Subtask 4 (10% số điểm): n ≤ 100, |t| ≤ 50 000;
• Subtask 5 (12% số điểm): |t| ≤ 100 000, S ≤ 100 000;
• Subtask 6 (10% số điểm): |t| ≤ 250 000, S ≤ 100 000;
• Subtask 7 (10% số điểm): |t| ≤ 500 000, S ≤ 100 000;
• Subtask 8 (10% số điểm): |t| ≤ 750 000, S ≤ 100 000;
• Subtask 9 (11% số điểm): Không có ràng buộc bổ sung.

---

(Thí sinh không được sử dụng tài liệu, Giám thị không giải thích gì thêm)