元宝 LeetCode 2902. 和带限制的子多重集合的数目 Python3实现

以下是 LeetCode 2902 题"和带限制的子多重集合的数目"的 Python3 实现代码。这个解决方案使用动态规划和多重背包优化技术，时间复杂度为 O(n + r·√Σ(nums[i]))，其中 n 是数组长度，r 是上限值。

from typing import List
from collections import Counter

class Solution:
def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
MOD = 1_000_000_007

# 1. 统计频率
counter = Counter(nums)

# 2. 处理数字0
zeros = counter.get(0, 0)
if 0 in counter:
del counter[0]

# 3. 动态规划数组
dp = [0] * (r + 1)
dp[0] = 1

# 4. 多重背包转移
for num, freq in counter.items():
# 如果数字大于r，可以跳过
if num > r:
continue

# 计算前缀和
prefix = dp[:] # 复制当前dp数组

# 计算不考虑次数限制的前缀和
for i in range(num, r + 1):
prefix[i] = (prefix[i] + prefix[i - num]) % MOD

# 更新dp，扣除超过freq次的方案
limit = num * (freq + 1)
for i in range(r, -1, -1):
if i >= limit:
dp[i] = (prefix[i] - prefix[i - limit]) % MOD
else:
dp[i] = prefix[i] % MOD

# 5. 累加区间[l, r]的方案数
result = 0
for i in range(l, r + 1):
result = (result + dp[i]) % MOD

# 6. 乘以0的贡献（每个0可选可不选）
return (result * (zeros + 1)) % MOD

# 测试用例
def test_solution():
solution = Solution()

# 测试用例1
nums1 = [1, 2, 2, 3]
l1, r1 = 3, 5
result1 = solution.countSubMultisets(nums1, l1, r1)
print(f"测试用例1: nums={nums1}, l={l1}, r={r1}")
print(f"结果: {result1}")
print()

# 测试用例2
nums2 = [0, 0, 1, 2, 3]
l2, r2 = 1, 3
result2 = solution.countSubMultisets(nums2, l2, r2)
print(f"测试用例2: nums={nums2}, l={l2}, r={r2}")
print(f"结果: {result2}")
print()

# 测试用例3
nums3 = [1, 1, 1, 1]
l3, r3 = 2, 3
result3 = solution.countSubMultisets(nums3, l3, r3)
print(f"测试用例3: nums={nums3}, l={l3}, r={r3}")
print(f"结果: {result3}")
print()

# 测试用例4
nums4 = [2, 3, 5]
l4, r4 = 5, 5
result4 = solution.countSubMultisets(nums4, l4, r4)
print(f"测试用例4: nums={nums4}, l={l4}, r={r4}")
print(f"结果: {result4}")
print()

# 测试用例5: 空集
nums5 = [1, 2, 3]
l5, r5 = 0, 0
result5 = solution.countSubMultisets(nums5, l5, r5)
print(f"测试用例5: nums={nums5}, l={l5}, r={r5}")
print(f"结果: {result5}")

if __name__ == "__main__":
test_solution()

关键点说明

1. 算法思路：

   • 使用多重背包的动态规划方法

   • 通过前缀和优化将时间复杂度从 O(n×r×cnt) 降低到 O(n×r)

   • 特殊处理数字0，因为它不影响和但影响方案数

2. 核心步骤：

   • 统计每个数字的出现频率

   • 处理数字0，因为0可以选择任意多个，但不会增加和

   • 使用动态规划计算每个可能的和的方案数

   • 对每个数字使用前缀和技巧优化多重背包转移

   • 最后累加[l, r]区间内的方案数，并乘以0的贡献

3. 时间复杂度：

   • 主要部分：O(r × 不同数字的个数)

   • 当r=2×10⁴时，这是可接受的

4. 空间复杂度：

   • O(r)，使用一维DP数组

   • 额外使用O(n)的空间存储频率统计

5. 边界情况处理：

   • 处理数字0的情况

   • 处理数字大于r的情况（可以直接跳过）

   • 处理空集合的情况（和为0）

这个实现能够高效地计算满足条件的子多重集合的数目，并正确处理各种边界情况。