2902：和带限制的子多重集合的数目（2758 分）

力扣第 115 场双周赛第 4 题

题目

给你一个下标从 0 开始的非负整数数组 nums 和两个整数 l 和 r 。

请你返回 nums 中子多重集合的和在闭区间 [l, r] 之间的 子多重集合的数目 。

由于答案可能很大，请你将答案对 109 + 7 取余后返回。

子多重集合 指的是从数组中选出一些元素构成的 无序 集合，每个元素 x 出现的次数可以是 0, 1, ..., occ[x] 次，其中 occ[x] 是元素 x 在数组中的出现次数。

注意：

• 如果两个子多重集合中的元素排序后一模一样，那么它们两个是相同的 子多重集合 。
• 空 集合的和是 0 。

示例 1：

输入：nums = [1,2,2,3], l = 6, r = 6
输出：1
解释：唯一和为 6 的子集合是 {1, 2, 3} 。

示例 2：

输入：nums = [2,1,4,2,7], l = 1, r = 5
输出：7
解释：和在闭区间 [1, 5] 之间的子多重集合为 {1} ，{2} ，{4} ，{2, 2} ，{1, 2} ，{1, 4} 和 {1, 2, 2} 。

示例 3：

输入：nums = [1,2,1,3,5,2], l = 3, r = 5
输出：9
解释：和在闭区间 [3, 5] 之间的子多重集合为 {3} ，{5} ，{1, 2} ，{1, 3} ，{2, 2} ，{2, 3} ，{1, 1, 2} ，{1, 1, 3} 和 {1, 2, 2} 。

提示：

• 1 <= nums.length <= 2 * 104
• 0 <= nums[i] <= 2 * 104
• nums 的和不超过 2 * 104 。
• 0 <= l <= r <= 2 * 104

相似问题：

• 0322：零钱兑换
• 0518：零钱兑换 II

分析

• 类似 2585，采用前缀和优化的多重背包即可
• 特别注意元素 0

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        mod = 10**9+7
        ct = Counter(nums)
        f = [1+ct[0]]+[0]*r
        del ct[0]
        for x,w in ct.items():
            for j in range(x,r+1):
                f[j] = (f[j]+f[j-x])%mod
            a = w*x+x
            for j in range(r,a-1,-1):
                f[j] = (f[j]-f[j-a])%mod
        return sum(f[l:])%mod

1771 ms