Counting Sub-Multisets with a Given Sum Range
IntuitionThe problem involves counting the number of multisets (subsets with repetitions allowed) that sum up within a given range [𝑙,𝑟].We need to efficiently
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves counting the number of multisets (subsets with repetitions allowed) that sum up within a given range [𝑙,𝑟].

We need to efficiently compute how many valid multisets exist that sum up to each value in this range.
Since the input can have duplicate elements, we need to ensure that each element is selected within its frequency limits.
A dynamic programming (DP) approach is suitable to efficiently compute the answer.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Preprocessing:

Count frequencies of all numbers in a using freq[x].
Filter unique elements into array b, skipping zeros initially.
Let n = b.size() (number of unique nonzero elements).
2. DP Definition:

Let dp[i][j] represent the number of ways to form sum j using elements from index i onward in b.
Base Case: If j = 0, there's always one way (empty set).
Initialize dp[n][j] = 1 for all j since an empty set can form any j.
3. DP Transition:

Iterate from last element to first (i from n-1 to 0).
4. At each step:
Inherit previous state: dp[i][j] = dp[i+1][j].
Include element b[i] up to its frequency using the standard DP approach for bounded knapsack.
Use inclusion-exclusion to ensure elements are counted within limits.
5. Final Computation:

Compute dp[0][r] - dp[0][l-1] to count multisets within the range.
Multiply by (1 + freq[0]) to account for zero values (which can be included in any subset).

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Preprocessing (frequency count & unique filtering): 𝑂(𝑛)
DP Table Computation:
Iterates over n elements and sums up to r, leading to 𝑂(𝑛⋅𝑟).
Final Computation: 𝑂(1).
Total Complexity: 𝑂(𝑛⋅𝑟), which is efficient for moderate constraints.
# Code
```cpp []
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
const int MOD = (int) 1e9 + 7;
template<ll mod = MOD>
struct mint {
    ll x;
    mint() : x(0) {}
    mint(ll _x) {
        _x %= mod;
        if (_x < 0) _x += mod;
        x = _x;
    }
    mint &operator+=(const mint &a) {
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    mint &operator-=(const mint &a) {
        x += mod - a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    mint &operator*=(const mint &a) {
        x = (ull) x * a.x % mod;
        return *this;
    }
    mint pow(ll pw) const {
        mint res = 1;
        mint cur = *this;
        while (pw) {
            if (pw & 1) res *= cur;
            cur *= cur;
            pw >>= 1;
        }
        return res;
    }
    mint inv() const {
        assert(x != 0);
        ll t = x;
        ll res = 1;
        while (t != 1) {
            ll z = mod / t;
            res = (ull) res * (mod - z) % mod;
            t = mod - t * z;
        }
        return res;
    }
    mint &operator/=(const mint &a) {
        return *this *= a.inv();
    }
    mint operator+(const mint &a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint &a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint &a) const {
        return mint(*this) *= a;
    }
    mint operator/(const mint &a) const {
        return mint(*this) /= a;
    }
    bool operator==(const mint &a) const {
        return x == a.x;
    }
    bool operator!=(const mint &a) const {
        return x != a.x;
    }
    bool operator<(const mint &a) const {
        return x < a.x;
    }
    friend ostream &operator<<(ostream &out, const mint &m) {
        out << m.x;
        return out;
    }
};
using Mint = mint<MOD>;
class Solution {
public:
    Mint dp[201][(int) 2e4 + 3];
    int freq[(int) 2e4 + 3];
    int countSubMultisets(vector<int>& a, int l, int r) {
    vi b;
    for (auto x: a) {
        if (freq[x] == 0 && x != 0)
            b.emplace_back(x);
        freq[x]++;
    }
    int n = b.size();
    for (int j = 0; j <= r; ++j) 
        dp[n][j] = 1;
    for (int i = n-1; i >= 0; --i){
        for (int j = 0; j <= r; ++j){
            dp[i][j] = dp[i+1][j];
            if (j-b[i] >= 0) {
                dp[i][j] += dp[i][j - b[i]];
                if (j-(freq[b[i]]+1)*b[i] >= 0)
                    dp[i][j] -= dp[i+1][j-(freq[b[i]]+1)*b[i]];
            }
        }
    }
    return ((dp[0][r] - (l-1 >= 0 ? dp[0][l-1] : 0))*(1+freq[0])).x;
    }
};
```
['Dynamic Programming', 'Sliding Window', 'C++']