Hướng dẫn cho TLEOJ Cup 2024 - Ngày 2 - Thần số học

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Ejen

Lời giải

Subtask 1:

$P \le 100, V = H \le 10^2$

Chỉ cần duyệt hết tất cả các bộ 3 rồi kiểm tra.

Subtask 2:

$P \le 100, V = H \le 10^4$

Tối ưu từ subtask 1 bằng dùng mảng đánh dấu.

Subtask 3:

$V = H$

Sử dụng mảng đánh dấu rồi duyệt hết các bộ 3 chữ số thay vì bộ 3 vị trí để kiểm tra.

Subtask 4:

$H \le 10^3$

Làm như đề bài yêu cầu.

Subtask 6:

$H \le 10^6$

Sàng trước rồi trả lời truy vấn bằng tổng tiền tố.

Subtask 7 + 8 + 9: Không có giới hạn gì thêm

Sử dụng quy hoạch động chữ số cơ bản.
Gọi $dp[pos][nonz][cnt0][cnt1][cnt2][cnt3]$ là số lượng số chủ đạo khi xét tới vị trí $pos$ có tiền tố là dãy có $cnt[0]$ chữ số chia hết cho $4$ , $cnt[1]$ chữ số chia $4$ dư $1$ , $cnt[2]$ chữ số chia $4$ dư $2$ , $cnt[3]$ chữ số chia $4$ dư $3$ và $nonz$ kiểm tra tiền tố có khác $0$ hay không.
Sàng trước mảng $ok[cnt0][cnt1][cnt2][cnt3]$ để kiểm tra.
Ta có $cnt0 \le 3, cnt1, cnt2, cnt3 \le 2$ vì $x + x + x$ chia hết cho $4$ khi $x$ chia hết cho $4$
Sử dụng truy vết để không cần khởi tạo lại mảng quy hoạch động sau mỗi truy vấn.

Bình luận

Không có bình luận nào.