Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án)

 Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
 ĐỀ SỐ 1
 BỘ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA 
 THPT - NĂM HỌC 2024-2025
 ĐỀ CHÍNH THỨC Môn: TIN HỌC
 Thời gian: 180 phút (Không kể thời gian giao đề)
 TỔNG QUAN ĐỀ THI
 Tiêu đề File chương trình File dữ liệu File kết quả
Bài 1 Người giao hàng SHIP.* SHIP.INP SHIP.OUT
Bài 2 Lập trình Robot AI ROAI.* ROAI.INP ROAI.OUT
Bài 3 Số nguyên dương PNUM.* PNUM.INP PNUM.OUT
- 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 bao gồm nhiều subtask, mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh 
được tính theo từng test đơn.
Hãy lập trình giải các bài toán sau:
Bài 1. Người giao hàng (7,0 điểm)
Ở một quốc gia nọ có N hòn đảo, được đánh số lần lượt từ 1 đến N. Có N-1 cây cầu, mỗi cây 
cầu nối trực tiếp 2 hòn đảo tạo thành một quần thể đảo mà giữa hai hòn đảo bất kì luôn tồn 
tại đường đi thông qua một cây cầu hoặc một dãy các cây cầu.
Tuấn là một người giao hàng của công ty VOI. Ban đầu Tuấn ở hòn đảo 1, được giao K 
nhiệm vụ giao hàng theo thứ tự từ 1 đến K và Tuấn phải xử lý các nhiệm vụ theo đúng thứ tự 
đó. Với nhiệm vụ thứ i(1 ≤ i ≤ K). Tuấn cần thực hiện giao hàng từ hòn đảo Ui đến hòn đảo 
Vi theo đường đi ghé qua ít hòn đảo nhất. Tuấn chỉ có thể thực hiện nhiệm vụ giao hàng thứ i 
nếu vị trí của Tuấn đang ở Ui và sau khi hoàn thành giao hàng thì vị trí của Tuấn sē là Vi. 
Lưu ý đối với mỗi nhiệm vụ, Tuấn có thể thực hiện hoặc từ chối giao hàng. Đối với mỗi hòn 
đảo, công ty đặt một giá trị phần thưởng mà người giao hàng có thể nhận được cho mỗi lần 
ghé qua. Với mỗi nhiệm vụ hoàn thành, Tuấn sẽ nhận được phần thưởng là giá trị lớn nhất 
trong số các giá trị của các hòn đảo nằm trên đường đi giao hàng, tính cả hòn đảo xuất phát 
và hòn đảo kết thúc.
Yêu cầu: Hãy tính tổng giá trị phần thưởng lớn nhất mà Tuấn có thể nhận được sau K nhiệm 
vụ.
Dữ liệu
Vào từ file văn bản SHIP.INP:
- Dòng đầu chứa một số nguyên N là số lượng hòn đảo (1 ≤ N ≤ 2 x 105)
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
- Dòng thứ hai chứa N số nguyên W1, W2,, WN là giá trị phần thưởng tại các hòn đảo 
 9
(0 ≤ W1, W2,, WN ≤ 10 )
- Mỗi dòng trong số N-1 dòng tiếp theo chứa 2 số nguyên dương thể hiện cây cầu kết nối 
giữa 2 hòn đảo.
- Dòng tiếp theo chứa một số nguyên K là số lượng nhiệm vụ (1 ≤ K ≤ 2 x 105).
- Dòng thứ I trong số K dòng tiếp theo chứa 2 số nguyên dương Ui và Vi thể hiện nhiệm vụ 
giao hàng thứ i (1 ≤ Ui , Vi ≤ N; Ui ≠ Vi)
Các số trên cùng một dòng cách nhau bởi dấu cách
Kết quả
Ghi ra file văn bản SHIP.OUT:
- Một số nguyên duy nhất thể hiện tổng giá trị phần thưởng lớn nhất mà Tuấn có thể nhận 
được sau K nhiệm vụ.
Ví dụ
 SHIP.INP SHIP.OUT Giải thích
4 6
1 2 3 4
1 2
2 3
3 4
4 
1 3
1 2
2 3
2 4 - Tuấn thực hiện các nhiệm vụ 2, 4 và từ chối các nhiệm 
 vụ 1, 3.
 - Tổng giá trị phần thưởng Tuấn nhận được là 2 + 4 = 6
7 37
1 5 5 7 3 16 1
1 4
1 2
2 3
4 5
5 6
5 7
7
1 3
3 2 - Tuấn thực hiện các nhiệm vụ 3, 4, 5, 7 và từ chối các 
 nhiệm vụ còn lại.
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
1 4 - Tổng giá trị phần thưởng Tuấn nhận được là 
4 2 7 + 7 + 7 + 16 = 37
2 5
5 7
5 6
Chấm điểm
- Subtask 1 (20% số điểm): N, K ≤ 100 và hòn đảo i có cây cầu nối với hòn đảo 
i + 1 (∀i: 1 ≤ i ≤ N – 1).
- Subtask 2 (20% số điểm): N ≤ 10 000 ; K ≤ 100 và hòn đảo i có cây cầu nối với hòn đảo 
i + 1 (∀i: 1 ≤ i ≤ N – 1).
- Subtask 3 (20% số điểm): Hòn đảo i có cây cầu nối với hòn đảo i + 1 (∀i: 1 ≤ i ≤ N – 1).
- Subtask 4 (20% số điểm): N ≤ 10 000 và K ≤ 100.
- Subtask 5 (20% số điểm): Không có ràng buộc nào thêm.
Bài 2. Lập trình Robot AI (7,0 điểm)
Trong cuộc thi trí tuệ nhân tạo ROAI2025, Ban tổ chức yêu cầu các đội chơi lập trình Robot 
AI trên sàn đấu trong môi trường thực tế ảo tham chiếu trên hệ trục tọa độ Oxy. Mỗi đội chơi 
cần đặt 2 con Robot AI tại 2 điểm phân biệt trên đường thẳng y = 2 với tọa độ x là số nguyên 
trong phạm vi từ 0 tới N. Mỗi Robot AI có một mắt thần có nhiệm vụ quan sát đường thẳng 
y = 0. Sàn đấu có hai tấm chắn biên là các đoạn thẳng AB và CD với tọa độ A(0,2), B(0,1), 
C(N, 1), D(N, 2). Ban tổ chức đặt thêm K tấm chắn khác là những đoạn thẳng nằm trên đoạn 
BC. Tấm chắn thứ i trong số K tấm chắn bắt đầu từ điểm (Li, 1) và kết thúc đơ điểm (Ri, 1).
Robot AI tại điểm U trên đường thẳng y = 2 chỉ quan sát được những điểm V trên đường 
thẳng nếu như đoạn thẳng UV không giao với bất kì đoạn thẳng là tấm chắn nào trong 
số K + 2 tấm chắn trên. Một đoạn trên đường thẳng y = 0 gọi là quan sát được nếu như mọi 
điểm trên đoạn thẳng đó (ngoại trừ 2 đầu mút) đều quan sát được. Nhiệm vụ của mỗi đội 
chơi là cần đặt được 2 con Robot AI sao cho tổng độ dài các đoạn quan sát được trên đường 
thẳng y = 0 bởi ít nhất một Robot AI là lớn nhất có thể.
Yêu cầu: Đội tuyển của Tuấn lần đầu tiên tham gia thi tài, hãy giúp đội của Tuấn tìm ra cách 
đặt tối ưu cho 2 con Robot AI.
Dữ liệu
Vào từ file văn bản ROAI.INP:
- Dòng đầu chứa hai số nguyên N và K (1 ≤ N ≤ 109; 1 ≤ K ≤ 2000)
- Dòng thứ i trong số K dòng tiếp theo chứa hai số nguyên Li và Ri (0 ≤ Li < Ri ≤ N)
Dữ liệu bảo đảm L1 < R1 < L2 < R2 <  < LK < RK. Các số trên cùng một dòng cách nhau 
bởi dấu cách
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
Kết quả
Ghi ra file văn bản ROAI.OUT:
- Một số nguyên duy nhất là tổng độ dài các đoạn quan sát được trên đường thẳng y = 0 
trong phương án tối ưu tìm được.
Ví dụ
 ROAI.INP ROAI.OUT
3 1 7
0 1
5 2 8
1 2
3 5
Giải thích
- Trong ví dụ 1, một phương án đặt vị trí tối ưu cho 2 Robot AI là x = 0 và x = 3. Robot AI 
thứ nhất quan sát được đoạn [2,6]; Robot AI thứ hai quan sát được đoạn [-1,3].
- Trong ví dụ 2, một phương án đặt vị trí tối ưu cho 2 Robot AI là x = 2 và x = 4. Robot AI 
thứ nhất quan sát được đoạn [-2,0] và đoạn [2,4]; Robot AI thứ hai quan sát được đoạn [-4,-
2] và đoạn [0,2].
Chấm điểm
- Subtask 1 (16% số điểm): N ≤ 200.
- Subtask 2 (16% số điểm): N ≤ 2000; K ≤ 20.
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
- Subtask 3 (16% số điểm): N ≤ 20000.
- Subtask 4 (20% số điểm): K ≤ 500.
- Subtask 5 (28% số điểm): Không có ràng buộc nào thêm.
Bài 3: Số nguyên dương (6,0 điểm)
Thầy giáo Lê rất yêu thích các bài toán số học và dãy số. Thầy định nghĩa trọng số của một 
số nguyên dương X (ký hiệu là W(X)) như sau:
- Đầu tiên, thầy Lê biểu diễn X thành dãy các chữ số của nó ở hệ cơ số 10, thu được dãy X1, 
X2,, XN với N là số chữ số của X;
- Nếu dãy chữ số của X có chứa hai phần tử đứng cạnh nhau có tổng chia hết cho 5, nghĩa là 
∃i ∈{1, 2,, N – 1} sao cho (Xi + Xi+1) ⋮ 5, thì W(X) = 0;
- Ngược lại, W(X) chính là số lượng dãy con gồm các phần tử liên tiếp trong dãy chữ số của 
X mà có kết quả xor các phần tử bằng 0. Cụ thể, W(X) là số lượng cặp i, j thoả mãn 1 ≤ i ≤ j 
≤ N và Xi ⊕ Xi+1 ⊕  ⊕ Xj = 0, với ⊕ là phép toán xor giữa hai số tự nhiên.
 Nhắc lại, với hai số tự nhiên a và b, phép toán a ⊕ b là phép toán xor từng bit tương ứng 
của a và b trong biểu diễn hệ nhị phân của chúng.
Ví dụ:
- W (1234) = 0 vì chứa hai chữ số 2 và 3 cạnh nhau có tổng chia hết cho 5;
- W (122103) = 5 vì không có hai chữ số nào cạnh nhau có tổng chia hết cho 5, đồng thời 
dãy chữ số của nó có 5 dãy con gồm các phần tử liên tiếp là (2,2), (1,2,2,1), (1,2,2,1,0), (0) 
và (2,1,0,3) có xor các phần tử bằng 0;
- W(3456) = 0 vì dãy chữ số của nó không có dãy con nào có xor các phần tử bằng 0.
Yêu cầu: Cho số nguyên dương k và các số nguyên dương L, H. Hãy tính tổng lũy thừa k 
của trọng số của tất cả các số nguyên dương nằm trong phạm vi [L, H], nghĩa là tính 
 k
∑ =퐿(W(X)) .
Dữ liệu
Vào từ file văn bản PNUM.INP:
- Dòng đầu chứa một số nguyên dương k là số lũy thừa trong tổng cần tính (1 ≤ k ≤ 2).
- Dòng thứ hai chứa một số nguyên dương T là số lượng trường hợp test (1 ≤ T ≤ 50000).
- Mỗi dòng trong số T dòng tiếp theo chứa hai số nguyên dương L và H mô tả một trường 
hợp test (1 ≤ L ≤ H ≤ 101000).
Dữ liệu bảo đảm tổng số chữ số của tất cả các số L và H trong một file dữ liệu vào không 
vượt quá 105. Các số trên cùng một dòng cách nhau bởi dấu cách.
 Kết quả
 Ghi ra file văn bản PNUM.OUT:
- Gồm T dòng, mỗi dòng chứa một số nguyên là phần dư của kết quả tìm được trong phép 
chia cho 1 000 000 007 tương ứng với trường hợp test trong dữ liệu đầu vào.
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
Ví dụ:
 PNUM.INP PNUM.OUT
1 1
3 5
1 10 12
100 105
111239 111245
2 1
3 7
1 10 30
100 105
111239 111245
Giải thích
Trong ví dụ thứ nhất:
- Ở trường hợp test thứ nhất: W(1), W(2), W(3), W(4), W(5), W(6),W(7), W(8), W(9), 
W(10) = 1, nên kết quả là 01 + 01+ 01+ 01+ 01+ 01+ 01+ 01+ 01+ 01 = 1.
- Ở trường hợp test thứ hai: W(100) = 0, W(101) = 2, W(102) = 1, W(103) = 1, W(104) = 1, 
W(105) = 0, nên kết quả là 01 + 21 + 11 + 11 + 11 + 01 = 5.
- Ở trường hợp test thứ ba: W(111239) = 0, W(111240) = 3, W(111241) = 0, W(111242) = 
2, W(111243) = 2, W(111244) = 3, W(111245) = 2, nên kết quả là 01 + 31 + 01 + 21 + 21 + 31 
+ 21 = 12
Trong ví dụ thứ hai:
- Ở trường hợp test thứ nhất: Kết quả là 02 + 02 + 02 + 02 + 02 + 02 + 02 + 02 + 02 + 12 = 1
- Ở trường hợp test thứ hai: Kết quả là 02 + 22 + 12 + 12 + 12 + 02 = 7.
- Ở trường hợp test thứ ba: Kết quả là 02 + 32 + 02 + 22 + 22 + 32 + 22 = 30.
Chấm điểm
- Subtask 1 (12% số điểm): T ≤ 10 và H ≤ 106.
- Subtask 2 (12% số điểm): T ≤ 10 và H ≤ 108 và k = 1.
- Subtask 3 (12% số điểm): H ≤ 1018 và k = 1
- Subtask 4 (12% số điểm): k = 1
- Subtask 5 (20% số điểm): T ≤ 10 và H ≤ 109 và k = 2.
- Subtask 6 (16% số điểm): L là luỹ thừa của 10; H = 10 x L - 1 và k = 2.
- Subtask 7 (16% số điểm): Không có ràng buộc nào thêm.
 ------------HẾT------------
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
 ĐÁP ÁN
Bài 1: Người giao hàng (7,0 điểm)
- Subtask 1 ( 20% số điểm): ,퐾 ≤ 100 và hòn đảo 푖 có cây cầu nối với hòn đảo 푖 +1 
(∀푖:1 ≤ 푖 ≤ ―1).
Hòn đảo 푖 có cây cầu nối với hòn đảo 푖 +1, bài toán tìm giá trị lớn nhất trên đường đi giữa 2 
hòn đảo ,푣 là bài toán tìm giá trị lớn nhất trên đoạn từ đến 푣.
Gọi [푖,푣] là giá trị phần thưởng có thể nhận được nhiều nhất sau nhiệm vụ 푖 và Tuấn đứng ở 
hòn đảo 푣.
Ở mỗi nhiệm vụ 푖,1 ≤ 푖 ≤ 퐾, ta có [푖,푣푖] = max( [푖 ― 1,푣푖], [푖 ― 1, 푖] + max푃 푡ℎ( 푖,푣푖) 
), trong đó maxPath( 푖,푣푖 ) là giá trị lớn nhất trong đoạn từ 푖 đến 푣푖 được xử lý bằng cách 
tìm kiếm tuần tự.
Độ phức tạp: ( 2 × 퐾).
- Subtask 2(20% số điểm): ≤ 10000;퐾 ≤ 100 và hòn đảo 푖 có cây cầu nối với hòn dảo 
푖 +1(∀푖:1 ≤ 푖 ≤ ―1).
Tương tự subtask 1. Thay tìm kiếm tuần tự trong maxPath ( 푖,푣푖) bằng tìm kiếm dựa trên 
Cây phân đoạn hoặc Bảng thưa.
Độ phức tạp: ( × 퐾 × log ).
- Subtask 3 (20% số điểm): Hòn đảo 푖 có cây cầu nối với hòn đảo 푖 +1(∀푖:1 ≤ 푖 ≤ ―1). 
Tương tự subtask 2. Gọi [푣푖] là giá trị phần thưởng có thể nhận được nhiều nhất sau khi 
hoàn thành thực hiện nhiệm vụ và kết thúc ở hòn đảo 푣푖, cập nhật [푣푖] = 
max( [푣푖], [ 푖] + maxPath ( 푖,푣푖)).
Độ phức tạp: ( × log + 퐾).
- Subtask 4 (20% số điểm): ≤ 10000 và 퐾 ≤ 100.
Tương tự subtask 3. Thay tìm kiếm tuần tự trong maxPath ( 푖,푣푖) bằng BFS để tìm đường đi 
và giá trị lớn nhất giữa 2 hòn đảo 푖 và 푣푖 trên cây.
Độ phức tạp: ( × 퐾).
- Subtask 5 ( 20% số điểm): Không có ràng buộc nào thêm.
Tương tự subtask 4. Thay BFS bằng kỹ thuật LCA và Bảng thưa để tính nhanh giá trị max 
trên đường đi giữa 2 hòn đảo và 푣.
Độ phức tạp: (( + 퐾) × log ).
Bài 2: Lập trình Robot AI (7,0 điểm)
- Subtask 1 (16% số điểm): ≤ 200.
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
 ×( 1)
Nhận thấy số lượng phương án của bài toán là . Với mỗi phương án, ta duyệt qua tất 
 2
cả các đoạn đơn vị từ ― tới 2 × để đánh dấu đoạn đơn vị được quan sát.
Độ phức tạp tính toán là ( 3).
- Subtask 2 (16% số điểm): ≤ 2000;퐾 ≤ 20.
Cải tiến từ Subtask 1, thay vì duyệt tất cả các đoạn đơn vị, ta tìm ra danh sách đoạn của mỗi 
Robot. Do danh sách đã được sắp xếp tăng dần, ta có thể gộp các đoạn và tính tổng độ dài 
trong tối đa 2 × 퐾 phép tính.
Độ phức tạp tính toán chung là ( 2 × 퐾).
- Subtask 3 (20% số điểm): ≤ 20000.
Nhận thấy, ta có thể cố định một Robot ở vị trí 0 mà không làm thay đổi lời giải tối ưu do 
tính chất tịnh tiến của bài toán. Tính chất tịnh tiến của bài toán là như sau: Phương án đặt hai 
Robot ở vị trí 1 và 2 sẽ tương đương với phương án đặt hai Robot ở vị trí 1 +Δ và 2 +Δ.
Do đó, số lượng phương án cần duyệt là ( ).
Độ phức tạp tính toán chung là ( × 퐾).
- Subtask 4 (20% số điểm): 퐾 ≤ 500.
Nếu phương án tối ưu không phải là phương án biên (Robot thứ nhất ở vị trí 0, Robot thứ hai 
ở vị trí ). Ta nhận thấy luôn tồn tại phương án tối ưu sao cho có ít nhất một đoạn quan sát 
được của Robot thứ nhất phải có mép (hai đầu mút 퐿푖,푅푖 ) trùng với một đầu mút (퐿푗 hoặc 
푅푗) của đoạn quan sát được của Robot thứ hai. Như vậy, bước đầu tiên, ra tìm ra tất cả 
khoảng cách thỏa mãn điều kiện trên. Số lượng các khoảng cách thỏa mãn là (퐾2). Với 
mỗi khoảng cách cố định, ta làm như subtask 2 để tìm ra độ dài quan sát được trong (퐾).
Độ phức tạp tính toán là (퐾3).
- Subtask 5 (28% số điểm): Không có ràng buộc nào thêm.
Ta xét bài toán tương đương sau:
Cho hai danh sách, danh sách thứ nhất là danh sách các vùng không quan sát được của Robot 
thứ nhất (Robot thứ nhất đặt ở vị trí 0); danh sách thứ hai là danh sách các vùng quan sát 
được của Robot thứ hai. Do danh sách thứ hai là các đoạn không giao nhau nên ta có thể xử 
lý từng đoạn của danh sách thứ hai. Trước hết với mỗi đoạn (푈 +Δ, +Δ), ta đánh dấu được 
 푖 푖
giá trị Δ1 là vị trí bắt đầu giao và Δ2 là vị trí kết thúc giao với đoạn [퐿푖,푅푖] của danh sách thứ 
 푖 푖
nhất. Ngoài ra, ta cũng cần xét Δ3 và Δ4 vị trí bắt đầu và kết thúc của việc hai đoạn lồng vào 
nhau. Ta cần sắp xếp lại các Δ và đưa vào mảng đánh dấu theo thứ tự xuất hiện.
Dùng kỹ thuật mảng cộng dồn và mảng hiệu, ta có thể tịnh tiến qua tất cả Δ. Mỗi lần tịnh tiến 
mất chi phí là (1).
Độ phức tạp tính toán là 퐾2log 퐾 .
Bài 3: Số nguyên dương (6,0 điểm)
 DeThiTinHoc.net Bộ 31 Đề thi HSG Quốc gia THPT môn Tin học (Có đáp án) - DeThiTinHoc.net
- Subtask 1: ≤ 10 và ≤ 106.
Tính trọng số của từng số từ 1 đến 106, sau đó tính tổng hoặc tổng bình phương trọng số các 
đoạn bằng cách sử dụng mảng cộng dồn.
Độ phức tạp: × log2 ( ) + .
- Subtask 2: ≤ 10; ≤ 1018 và = 1.
Đổi thứ tự tính: Xét lần lượt các cập (푖,푗) mà 1 ≤ 푖 ≤ 푗 ≤ 19; sau đó đếm số lượng số trong 
phạm vi [퐿, ] thỏa mãn 푖 ⊕ 푖+1 ⊕  ⊕ 푗 = 0; và không chứa hai chữ số nào cạnh nhau 
có tổng chia hết cho 5 . Bài toán đếm này có thể giải quyết bằng quy hoạch động chữ số, có 
thể cài đặt bằng đệ quy và sử dụng mảng nhớ.
Độ phức tạp: × log3 ( ) , với hằng số thuật toán là 16 × 5 × 10.
- Subtask 3: ≤ 1018 và = 1.
Tương tự subtask 2, nhưng xử lý bài toán đếm chung cho tất cả các trường hợp test; sau đó 
tìm thứ tự từ điển của và 퐿 ―1 trong dãy nghiệm đếm được.
Độ phức tạp phần tiền xử lý: log3 ( ) với hằng số thuật toán là 16 × 5 × 10.
Độ phức tạp phần trả lời các trường hợp test: × log2 ( ) , với hằng số thuật toán là 10 
và là tổng số chữ số của tất cả các số 퐿 và trong các trường hợp test.
- Subtask 4: = 1.
Thay vì xét từng cặp (푖,푗); có thể xét cấu hình nghiệm có dạng bộ hai số ( , ) với 
 = 1, 2,, 푛 là một dãy thập phân và = 1, 2,, 푛 là một dãy nhị phân có các bit 1 kề 
nhau. Các cấu hình cần thoả mãn: không chứa hai chữ số cạnh nhau có tổng chia hết cho 5; 
các bit 1 của đánh dấu các chữ số tương ứng trên sao cho xor của chúng bằng 0. Có thể 
đếm số cấu hình như vậy bằng cách đệ quy xây dựng từng vị trí của cả hai số ( , ) cùng một 
lúc; sau đó sử dụng mảng nhớ để khử trùng lặp các bài toán. Để kiểm soát phạm vi của cho 
từng trường hợp test, có thể sử dụng kỹ thuật tìm thứ tự từ điển của nghiệm như sau: Để đếm 
số cấu hình bé hơn , ta có thể
xét 푖 là vị trí đầu tiên mà 푖 < 푖, và xét hết các khả năng của có thể có tính đến 푖. Mặc dù 
số khả năng của lớn, nhưng giá trị xor của các chữ số tương ứng là bé hơn 16; do đó có thể 
xét các giá trị xor này.
Độ phức tạp phần tiền xử lý: (log ( )) với hằng số thuật toán là 16 × 5 × 20.
Độ phức tạp phần trả lời các trường hợp test: × log2 ( ) , với hằng số thuật toán là 20 
và là tổng số chữ số của tất cả các số 퐿 và trong các trường hợp test.
- Subtask 5: ≤ 10; ≤ 109 và = 2.
Bình phương trọng số của một số = 1, 2,, 푛 chính là số lượng bộ bốn số (푖,푗, ,푡) sao 
cho 1 ≤ 푖 ≤ 푗 ≤ 푛;1 ≤ ≤ 푡 ≤ 푛 và 푖 ⊕ 푖+1 ⊕  ⊕ 푗 = ⊕ +1 ⊕  ⊕ 푡 = 0.
Ý tưởng đổi thứ tự tính, tương tự như subtask 2: Xét tất cả các bộ bốn số (푖,푗, ,푡) và đưa về 
 DeThiTinHoc.net