dp knackbag
Intuition\ncount of unique positive numbers <=  sqrt(nums[i]) \n\n# Complexity\n- Time complexity: O(r * sqrt(sum(nums[i])))\n\n- Space complexity: O(r)\n\n# Co
# Intuition\ncount of unique positive numbers <= $$ sqrt(nums[i]) $$\n\n# Complexity\n- Time complexity: $$O(r * sqrt(sum(nums[i])))$$\n\n- Space complexity: $$O(r)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int countSubMultisets(const vector<int> &nums, int l, int r) {\n        map<int, int> m;\n        long long zeroes = 0;\n        for (const auto it : nums)\n            if (it != 0) ++m[it];\n            else ++zeroes;\n        const vector<pair<const int, int>> v(m.cbegin(), m.cend());\n        int n = v.size();\n        vector<vector<int>> dp(2, vector<int>(r + 1, 0));\n        dp[0][0] = 1;\n        const int mod = 1e9 + 7;\n        for (int i = 0; i < n; ++i) {\n            vector<int> sums(v[i].first, 0);\n            for (int su = 0; su <= r; ++su) {\n                sums[su % v[i].first] = (sums[su % v[i].first] + dp[0][su]) % mod;\n                if (su - v[i].first * (v[i].second + 1) >= 0) {\n                    sums[su % v[i].first] = (mod + sums[su % v[i].first] - dp[0][su - v[i].first * (v[i].second + 1)]) % mod;\n                }\n                dp[1][su] = sums[su % v[i].first];\n            }\n            swap(dp[0], dp[1]);\n        }\n        long long ans = 0;\n        for (int i = l; i <= r; ++i) {\n            ans = (ans + dp[0][i]) % mod;\n        }\n        ans = (ans * (zeroes + 1)) % mod;\n        return ans;\n    }\n};\n```
['C++']