The secret: faster than 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe dirty secret of this problem is that the distinct values in the array cannot be ver
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe dirty secret of this problem is that the distinct values in the array cannot be very many.\nIndeed, the sum of the first $n$ natural numbers is $\\frac {n(n+1)} 2$. It is given in the problem that the sum of all values is no more than $20,000$. Thus, there cannot be more than $200$ distinct values in the array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe need an algorithm that deals well with values of high multiplicity.\nSuch an algorithm is given in a simplified and straightforward form below.\nLet $c_0, \\ldots, c_r$ be the list of the counts, that is the number of ways each value $0, \\ldots, r$ can be obtained as a sum. In the beginning, $c_0=1$ and all the other counts are $0$.\nFor a number $n$ in the array with multiplicity $m$, the list gets updated as follows:\n$c_k$ gets replaced by $c_k + c_{k-n} + \\ldots + c_{k-mn}$, where the terms with negative indices are $0$.\nWe can do this summation in just two passes through the list of length $r$, so this only takes $O(r)$ time. In the first pass, we compute the partial sums and replace $c_k$ by\n$c_k + c_{k-n} + c_{k-2n} + \\ldots + c_{k-jn} + \\ldots$,\ndisregarding $m$. In the second pass we take the differences of these partial sums in order to truncate at $k-mn$.\n\nWe can go through the distinct values in the array in any order, but it is useful to consider $0$ separately. Having $0$ in the array with multiplicity $m$ just means that every count $c_k$ in the list gets multiplied by $m+1$.\n\nThe final answer is the sum of the counts in the desired range.\n\n# Complexity\n- Time complexity: $O(\\min(s, r) n)$, where $n$ is the number of distinct values in the array, $s$ is the sum of all values, and $r$ is the right endpoint of the interval.\n\nDoing this naively, without taking advantage of multiplicity, as I tried during the contest, results in a factor that is the total number of values in the array, not just the number of distinct values. Such a solution will potentially be up to $100$ times slower than the above and will exceed the time limit.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(\\min(s, r))$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        s=sum(nums)\n        if l>s:\n            return 0\n        r=min(r, s)\n        d=defaultdict(int)\n        for n in nums:\n            d[n]+=1\n        lst=list(d.items())\n        lst.sort(key=lambda x:-x[0])\n        mult=1\n        if lst[-1][0]==0:\n            mult+=lst.pop()[1]\n        p=10**9+7\n        dct=[0]*(r+1)\n        dct[0]=1\n        for k, (n, m) in enumerate(lst):\n            for cur in range(r-n+1):\n                dct[cur+n]+=dct[cur]\n            m=n*(m+1)\n            for cur in range(r, m-1, -1):\n                dct[cur]-=dct[cur-m]\n            if k%20==0:\n                for val in range(r+1):\n                    dct[val]%=p\n        return sum(dct[val] for val in range(l, r+1))*mult%p\n```
['Python3']