[Python] Numpy-powered O(NR) code (Beats 90%)
Approach\n Describe your approach to solving the problem. \nThanks to numpy that is optimized for vector computation, you can get AC with $O(NR)$ code. Actually
# Approach\n<!-- Describe your approach to solving the problem. -->\nThanks to numpy that is optimized for vector computation, you can get AC with $O(NR)$ code. Actually, it is pretty fast!\nAs an illustration, for `nums = [1, 3, 3]`, the code works as follows:\n- For `num = 1`, add a vector shifted right by 1 into `dp`.\n```\n+---------+-----+-----+-----+-----+-----+-----+-----+-----+-----+\n| index   |   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |\n+=========+=====+=====+=====+=====+=====+=====+=====+=====+=====+\n| dp      |   1 |   0 |   0 |   0 |   0 |   0 |   0 |   0 |   0 |\n+---------+-----+-----+-----+-----+-----+-----+-----+-----+-----+\n| dp >> 1 |     |   1 |   0 |   0 |   0 |   0 |   0 |   0 |   0 |\n+=========+=====+=====+=====+=====+=====+=====+=====+=====+=====+\n| result  |   1 |   1 |   0 |   0 |   0 |   0 |   0 |   0 |   0 |\n+---------+-----+-----+-----+-----+-----+-----+-----+-----+-----+\n```\n- For 2 occurrences of `num = 3`, add vectors shifted right by 3 and 6 into `dp`.\n```\n+---------+-----+-----+-----+-----+-----+-----+-----+-----+-----+\n| index   |   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |\n+=========+=====+=====+=====+=====+=====+=====+=====+=====+=====+\n| dp      |   1 |   1 |   0 |   0 |   0 |   0 |   0 |   0 |   0 |\n+---------+-----+-----+-----+-----+-----+-----+-----+-----+-----+\n| dp >> 3 |     |     |     |   1 |   1 |   0 |   0 |   0 |   0 |\n+---------+-----+-----+-----+-----+-----+-----+-----+-----+-----+\n| dp >> 6 |     |     |     |     |     |     |   1 |   1 |   0 |\n+=========+=====+=====+=====+=====+=====+=====+=====+=====+=====+\n| result  |   1 |   1 |   0 |   1 |   1 |   0 |   1 |   1 |   0 |\n+---------+-----+-----+-----+-----+-----+-----+-----+-----+-----+\n```\n\n# Complexity\n- Time complexity: $O(NR)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N + R)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom collections import Counter\nimport numpy as np\n\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        mod = 10**9 + 7\n        count = Counter(nums)\n        dp = np.zeros(r + 1, dtype=np.int64)\n        dp[0] = 1\n        for num in count:\n            if num == 0:\n                continue\n            dpnew = np.array(dp)\n            for i in range(1, count[num] + 1):\n                dpnew[num*i:] += dp[:-num*i]\n            dp = dpnew % mod\n        return (count[0] + 1) * sum(dp[l:r+1]) % mod\n```
['Python3']