以下是 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）

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