Knapsack DP + Pack Update Trick (Sliding Window)
Intuition\nKnapsack DP. See also lee215\'s solution.\n\n \u274C(Low to High) One approach is given a dp[j] > 0, update dp[j+i], dp[j+2i], ... dp[j+ci]. But this
# Intuition\nKnapsack DP. See also [lee215\'s solution](https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum/solutions/4168129/c-python-knapsack-dp/).\n\n* \u274C(Low to High) One approach is given a `dp[j] > 0`, update `dp[j+i]`, `dp[j+2i]`, ... `dp[j+ci]`. But this leads to $$O(nr\\mathrm{max}(c))$$ time where $n$ is the num of different numbers.\n* \u2705(High to Low) The other approach is to a "Pack Update Trick":\n   $$\\mathrm{dp}_j+=\\mathrm{dp}_{j-i}+\\mathrm{dp}_{j-2i}+\\cdots+\\mathrm{dp}_{j-ci}$$\n   $$\\mathrm{dp}_{j-i}+=\\mathrm{dp}_{j-2i}+\\cdots+\\mathrm{dp}_{j-ci}+\\mathrm{dp}_{j-(c+1)i}$$\n  The "pack update" is a sliding window. This leads to $$O(n\\mathrm{max}(i)\\mathrm{max}(c))$$ time.\n\n\n# Approach\nConsider this sequence and update them from hi to lo:\n$$r-(c+1)i$$, $$r-ci$$, ..., $$r-2i$$, $$r-i$$, $$r$$.\n\nThen do the same for\n$$r-1-(c+1)i$$, $$r-1-ci$$, ..., $$r-1-2i$$, $$r-1-i$$, $$r-1$$.\n\nand so on.\n\n\n\n# Complexity\n- Time complexity: $$O(n\\mathrm{max}(i)\\mathrm{max}(c))$$\n- Space complexity: $$O(n+r)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    using ll = long long;\n    static constexpr ll M = 1\'000\'000\'007;\n    static void Add(ll& x, ll y) { x = (x + y) % M; }\n    int countSubMultisets(vector<int>& a, int l, int r) {\n        vector<ll> dp(r + 1, 0);\n        dp[0] = 1;\n        unordered_map<int, int> s;\n        for (int i : a) s[i]++;\n        for (const auto [i, c] : s) {\n            if (i == 0) continue;\n            for (int j = r; j >= r-i+1; --j) {\n                ll pack = 0;\n                for (int k = 1; k <= c && j-k*i >= 0; ++k) {\n                    Add(pack, dp[j-k*i]);\n                }\n                for (int l = j; l-i >= 0; l -= i) {\n                    Add(dp[l], pack);\n                    for (pack -= dp[l-i]; pack < 0; pack += M);\n                    if (l-(c+1)*i >= 0) Add(pack, dp[l-(c+1)*i]);\n                }\n            }\n        }\n        ll ans = 0;\n        for (int i = l; i <= r; ++i) {\n            Add(ans, dp[i]);\n        }\n        return ans * (s[0] + 1) % M;\n    }\n};\n```\n\n# Similar Problems\nTODO
['Dynamic Programming', 'Sliding Window', 'C++']