【动态规划】【同余前缀和】【多重背包】[推荐]2902. 和带限制的子多重集合的数目，和带限制的子多重集合数目与动态规划、同余前缀和、多重背包问题的解析

摘要：本文探讨了动态规划中的多重背包问题，并引入同余前缀和的概念。文章主要介绍了如何计算带有特定限制的子多重集合的数目。通过深入探讨算法原理，给出了相关问题的解决方案，并提供了推荐资料。该研究成果对于解决多重背包问题具有一定的指导意义。

本文涉及知识点

动态规划汇总

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

C++算法：滑动窗口总结

多重背包

LeetCode2902. 和带限制的子多重集合的数目

给你一个下标从 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 public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return *this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return *this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator*=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator return m_iData