Hướng dẫn giải của Đếm Tập Con Có Tổng Chia Hết Cho M
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ác giả:
Định nghĩa DP theo modulo
Đặt ~dp[r]~ = số tập con (kể cả rỗng) có tổng ≡ ~r~ (mod ~M~).
Khởi tạo: ~dp[0] = 1~ (tập rỗng).
Công thức chuyển trạng thái
Với mỗi phần tử ~a_i~, tạo mảng tạm ~ndp~: $$ndp[(r + a_i) \bmod M] += dp[r]$$
Để tránh dùng cùng phần tử hai lần (0/1), ta dùng bản sao của ~dp~ để cập nhật.
Kết quả
~dp[0] - 1~ (trừ tập rỗng).
Phân tích độ phức tạp
- Thời gian: ~O(N \times M)~ với ~N, M \le 1000~: ~10^6~ thao tác.
- Bộ nhớ: ~O(M)~
Công thức đóng (tối ưu)
Sử dụng căn nguyên thủy và DFT trên vành số modular có thể giải trong ~O(N + M \log M)~, nhưng cách DP đủ nhanh cho giới hạn đề bài.
Bình luận