Python || dynamic programming || 90ms
First we group nums by n % k. These buckets are disjoint, we could compute the number of beautiful subsets for each bucket(including empty set), and the product
1. First we group `nums` by `n % k`. These buckets are disjoint, we could compute the number of beautiful subsets for each bucket(including empty set), and the product of these numbers minus 1 would be the answer.\n2. For each bucket, use dynamic programming. Here we consider an example, [2,2,2,4,4,6], `k = 2`.\n![image](https://assets.leetcode.com/users/images/1ed9628e-5e11-4b4d-ad95-dd6962cf24cc_1680187738.536953.png)\nFirst we consider only 2. There are `2**3-1 = 7` subsets containing 2, and `1` subset not containing 2(empty), i.e. `dp_y = 7, dp_n = 1`.\nNext we consider 4. If we choose to have 4 in our subsets, it cannot come from those subsets containing 2, i.e. `dp_y = 1*(2**2-1) = 3`. If we choose not to have 4, it can come from either subsets containing 2 or not, i.e. `dp_n = 7+1 = 8`.\nFinally we consider 6. Similar to above, we have `dp_y = 8*1 = 8, dp_n = 3+8 = 11`.\nSo the number of all possibilities(including empty set) is the sum of the rightmost column, `8+11 = 19`.\n```\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:\n        buckets = [[] for _ in range(k)]\n        for n in nums:\n            buckets[n % k].append(n)\n        \n        def dp(bu):\n            cnt = Counter(bu)\n            arr = sorted((key, val) for key, val in cnt.items())\n            dp_y, dp_n = 2**arr[0][1]-1, 1\n            for i, (key, val) in enumerate(arr[1:], start=1):\n                tmp = 2**val-1\n                if key - arr[i-1][0] == k:\n                    dp_y, dp_n = dp_n*tmp, dp_y+dp_n\n                else:\n                    dp_y, dp_n = (dp_y+dp_n)*tmp, dp_y+dp_n\n            return dp_y + dp_n\n        \n        ans = 1\n        for bu in buckets:\n            if bu:\n                ans *= dp(bu)\n        return ans - 1
['Dynamic Programming', 'Python3']