knapsack multiset
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countSubMultisets(vector<int>& a, int l, int r) {\n        const int mod = 1e9 + 7;\n        const int n = a.size();\n        // \n        map<int,int> mp; // val - cnt\n        for(auto&x:a) mp[x]++;\n        // knapsack\n        vector<int> dp(r+1);\n        dp[0] = 1;\n        // Ex val, cnt = 2 3\n        // dp = 1 2 3 4 5 6 7 8 9 10\n        //          1 2 3 4 5 6 7 8\n        //              1 2 3 4 5 6\n        //                  1 2 3 4\n        for(auto&[val, cnt]:mp) {\n            if(val == 0) continue;\n            for(int i = r; i >= max(0,r-val+1); i--) {  // 10, 9\n                int sum = 0;\n                for(int j=0; j<cnt; j++) { // (10), (8), (6)\n                    if(i-j*val >= 0) sum = (sum + dp[i-j*val])%mod;\n                }\n                for(int j=i; j>=0; j-=val) {  // 10, 8, 6, 4, 2, 0\n                    sum = (sum - dp[j] + mod)%mod;\n                    if(j-val*cnt >= 0) sum = (sum + dp[j-val*cnt])%mod;\n                    dp[j] = (dp[j] + sum)%mod;\n                }\n            }\n        }\n        // res\n        int64_t res = 0;\n        for(int i=l; i<=r; i++) {\n            res = (res + dp[i])%mod;\n        }\n        return (res*(mp[0]+1))%mod;\n    }\n};\n```
['C++']