Hướng dẫn giải của [TS10 Nghệ An 2025 - 2026] Hộp quà may mắn
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ý tưởng
Điều kiện tổng chữ số chia hết cho ~3~ tương đương số đó chia hết cho ~3~. Vì ~\gcd(97,3)=1~, số cần đếm chia hết cho ~291~. Dùng DP theo phần dư: ~dp[r]~ là số xâu con kết thúc ở vị trí trước có phần dư ~r~ modulo ~291~. Khi thêm chữ số mới, cập nhật phần dư ~(r\cdot 10+d) \bmod 291~ và thêm xâu con chỉ gồm chữ số hiện tại.
Độ phức tạp
~O(291\cdot |S|)~.
Bình luận