Hướng dẫn giải của Đếm Tập Con Trong Đoạn Tổng
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ả:
Ý tưởng
Tính mảng ~dp[j]~ = số tập con (kể cả rỗng) có tổng đúng bằng ~j~, sau đó cộng các giá trị ~dp[L], dp[L+1], \ldots, dp[R]~.
Chú ý: Trừ đi tập rỗng nếu ~L = 0~.
Định nghĩa DP
~dp[j]~ = số tập con có tổng ~j~. Dùng 0/1 Knapsack: duyệt ~j~ từ lớn về nhỏ.
Kết quả
$$\text{ans} = \sum_{j=L}^{\min(R, \text{maxSum})} dp[j] \pmod{10^9+7}$$
Nếu ~L = 0~, bài cho tập không rỗng, cần trừ ~dp[0] = 1~... nhưng theo đề không cho ~L = 0~, hoặc ta trừ riêng.
Thực tế đề yêu cầu tập không rỗng, nên nếu ~L \le 0~, câu trả lời cần trừ ~1~.
Độ phức tạp
- Thời gian: ~O(N \times \text{maxSum})~ với maxSum ~\le N \times \max(a_i) = 10000~
- Bộ nhớ: ~O(\text{maxSum})~
Bình luận