🔥🔥🔥 C++ Solution 🔥🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe number of unique elements can be at most 200. We can optimize our dp using that use
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe number of unique elements can be at most 200. We can optimize our dp using that use sliding window. We get this number by approximating sqrt(n). \n# Approach\ndp[i] is the number of unique sorted multisets of sum i lets say that we use a new number, a that occurs c times within the array we can add a 1 to c times to every multiset to create new ones, so the dp transition will look like dp[i] += dp[i - a] + dp[i - a * 2] + ... + dp[i - a * c] \n\nSince the sum of c across all a is n, doing dp like this will result in n^2 time complexity. We can speed up the update for each pair of a, c by using sliding window. We do this by\nwe want to add to dp[i] dp[i - a] + dp[i - a * 2] + ... + dp[i - a * c]. \n\nNote that the stuff we add to dp[i - a] is very similar: dp[i - a * 2] + dp[i - a * 3] + ... + dp[i - a * (c + 1)] dp[i - a] got removed, and dp[i - a * (c + 1)] got added once you know the amount to add for dp[i], it takes constant time to compute the amount to add for dp[i - a]. \n\nI claim that when sped up, each pair will only take O(n) time to process and since the number of unique a is at most 200.\n\n# Complexity\n- Time complexity: $$O(200n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(200n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ntypedef long long ll;\nconst ll MOD = 1e9 + 7;\n\nclass Solution {\npublic:\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        const ll N = 2e4;\n        vector<ll> dp(N + 1);\n        map<ll,ll> m;\n        dp[0] = 1;\n        m[0] = 1;\n        for(auto x : nums) {\n            m[x]++;\n        }\n        ll mult = m[0]; m.erase(0);\n        for(auto x : m) {\n            //{a, c}\n            ll a = x.first;\n            ll c = x.second;\n            vector<ll> help(N + 1);\n            for(int i = 1; i <= N; i++) {\n                ll sum = 0;\n                if(i - a >= 0) {\n                    sum += dp[i-a];\n                    sum += help[i-a];\n                }\n                if(i - a * (c + 1) >= 0) {\n                    sum -= dp[i - a * (c + 1)];\n                }\n                help[i] = (sum + MOD) % MOD;\n            }\n            for(int i = 0; i <= N; i++) {\n                dp[i] += help[i];\n                if(dp[i] >= MOD) dp[i] -= MOD;\n            }\n        }\n        ll sum = 0;\n        for(int i = l; i <= r; i++) {\n            sum += dp[i];\n            if(sum >= MOD) sum -= MOD;\n        }\n        return sum * mult % MOD;\n    }\n};\n```\n\n# Upvote if you found this helpful :)
['Dynamic Programming', 'C++']