13-Line Solution with DP in Python
Intuition\n Describe your first thoughts on how to solve this problem. \nNaive $O(NM)$ DP is too slow for the test size. However, the size of distinct numbers i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNaive $O(NM)$ DP is too slow for the test size. However, the size of distinct numbers is up to $O(\\sqrt{N})$ only, so we try to find a DP solution that adds each distinct number in $O(N)$. As a result, the overall complexity is $O(N\\sqrt{N}) = O(N^{1.5})$, which is fast enough for passing the test cases. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet $S(i, j)$ is the ways to make a summation of $j$ with the distinct elements $v_1, v_2, ..., v_i$.\nFor the distinct number $v_i$, which appears $k_i$ times, \n$S(i, j) = S(i-1, j) + S(i-1, j-v_i) + S(i-1, j-2v_i) + ... + S(i-1, j-k_i v_i) $\nSo we can maintain $v_i$ sliding windows to keep $S(i-1, j-v_i) + S(i-1, j-2v_i) + ... + S(i-1, j-k_i v_i)$. \nIn this way, each distinct number can be processed in $O(N)$ only.\nThe number of distinct number is $O(\\sqrt{N})$, so the overall complexity is $O(N^{1.5})$.\n\n# Complexity\n- Time complexity: $O(N^{1.5})$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N)$\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        cnt = Counter(nums)\n        prev = [1 + cnt[0]] + [0] * r\n        for v, k in cnt.items():\n            if v > 0:\n                current = [0] * (r+1)\n                table = [0] * v\n                for j in range(v, r+1):\n                    table[j % v] += prev[j - v]\n                    current[j] += table[j % v]\n                    if j - v * k >= 0:\n                        table[j % v] -= prev[j - v * k]\n                prev = [(a + b) % 1000000007 for a, b in zip(prev, current)]\n        return sum(prev[l:r+1]) % 1000000007\n```
['Dynamic Programming', 'Sliding Window', 'Python3']