题目描述
给你一个下标从 0 开始的非负整数数组 nums
和两个整数 l
和 r
。
请你返回 nums
中子多重集合的和在闭区间 [l, r]
之间的 子多重集合的数目。
由于答案可能很大,请你将答案对 10^9 + 7
取余后返回。
子多重集合 指的是从数组中选出一些元素构成的 无序 集合,每个元素 x
出现的次数可以是 0, 1, ..., occ[x]
次,其中 occ[x]
是元素 x
在数组中的出现次数。
注意:
- 如果两个子多重集合中的元素排序后一模一样,那么它们两个是相同的 子多重集合。
- 空 集合的和是
0
。
样例
输入:nums = [1,2,2,3], l = 6, r = 6
输出:1
解释:唯一和为 6 的子集合是 {1, 2, 3}。
输入: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}。
输入: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 * 10^4
0 <= nums[i] <= 2 * 10^4
nums
的和不超过2 * 10^4
。0 <= l <= r <= 2 * 10^4
算法
(动态规划) $O(n + m \sqrt m)$
- 先考虑暴力的动态规划。设状态 $f(i, j)$ 表示枚举了前 $i$ 种数字,组成为 $j$ 的子多重集合的方案数。
- 初始时,$f(0, 0) = 1$,其余为 $0$。
- 转移时,对于第 $i$ 种数字,假设其出现次数为 $cnt(i)$,则分别枚举 $j$ 和 $k$,转移 $f(i, j) = f(i, j) + f(i - 1, j - k * i)$。
- 最终答案为 $f(n - 1, l) + f(n - 1, l + 1) + \dots + f(n - 1, r)$。
- 假设 $m$ 为数字的总和,直接暴力动态规划无论是时间还是空间都是 $O(nm)$ 的,不可接受。
- 对于空间的优化,可以采用 01 背包的策略,可以倒序枚举 $j$ 省略掉第一维。此时需要注意,数字 $0$ 需要特殊处理,不能作为一种数字参与动态规划,最后返回答案乘上 $0$ 的出现次数。
- 对于时间的优化,考虑去除 $k$ 这一维的枚举。注意到,每次转移都是取 $j - k, j - 2k, j - xk$ 的和转移到 $j$ 上,所以每种数字,都可以维护 $i$ 个部分和,每次转移直接从 $j%i$ 的部分和中转移。但需要注意,此时倒序枚举的空间优化会失效,可以采用临时数组的方式避免从自身转移。
时间复杂度
- 需要 $O(n)$ 的时间预处理每种数字的出现次数。
- 最多有 $O(\sqrt m)$ 种数字参与到第一层循环中,每次循环只需要 $O(m)$ 的时间转移,故总时间复杂度为 $O(n + m \sqrt m)$。
空间复杂度
- 需要 $O(m)$ 的额外空间存储每种数字的出现次数、动态规划的状态和部分和数组。
C++ 代码
#define LL long long
const int N = 20010;
class Solution {
private:
int f[N], cnt[N], t[N], s[N];
public:
int countSubMultisets(vector<int>& nums, int l, int r) {
const int mod = 1000000007;
const int n = nums.size();
for (int i = 0; i < n; i++)
++cnt[nums[i]];
f[0] = 1;
int sum = 0;
for (int i = 1; i < N; i++) {
if (cnt[i] == 0)
continue;
sum += cnt[i] * i;
for (int j = 0; j <= min(r, sum); j++) {
if (j / i == 0)
s[j % i] = 0;
t[j] = f[j];
f[j] = (f[j] + s[j % i]) % mod;
s[j % i] = (s[j % i] + t[j]) % mod;
if (j >= i * cnt[i])
s[j % i] = (s[j % i] - t[j - i * cnt[i]] + mod) % mod;
}
}
int ans = 0;
for (int i = l; i <= r; i++)
ans = (ans + f[i]) % mod;
return (LL)(ans) * (cnt[0] + 1) % mod;
}
};