【LeetCode第115场双周赛】100029. 和带限制的子多重集合的数目 | 前缀和背包 | 中等

题目内容

原题链接

给定一个长度为 $n$ 的数组 $nums$ 和一个区间左右端点 $[l,r]$ 。
返回 $nums$ 中子多重集合的和在闭区间 $[l,r]$ 之间的 子多重集合的数目 。

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

注意：

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

数据范围

• $1\le n\le 2\cdot 10^4$
• $0\le nums[i]\le 2\cdot 10^4,sum(nums)\le 2\cdot 10^4$
• $0\le l\le r\le 2\cdot 10^4$

题解

本题从数据范围出发。

考虑 $nums$ 总和不超过 $20000$ ，那么 $nums$ 中不同的数有多少个呢？

考虑最小的情况下有 $x$ 种数，每种数一个，那么总和为：$\frac{x\times (x+1)}{2}$
当 $x=200$ 时，$\frac{x\times (x+1)}{2}=20100>20000$ ，故至多有 $199$ 个不同的数。

那么问题转换为一个分组背包问题，值为 $v$ 的数的个数有 $c$ 个，那么可以选择这个数 $[0,v]$ 次，这样可以转换成 $01$ 背包，最多有 $O(n)$ 个物品。

这样时间复杂度为：$O(n\sum nums)$ ，$4e8$ 不能通过。

考虑从定义出发：
$dp[i][j]$ 表示前 $i$ 种物品，容量使用为 $j$ 的方案数。
那么 $dp[i][j]$ 的状态转移方程是什么呢？

$dp[i][j]=\sum _{k}dp[i-1][k]$ ，满足 $0\le j-k\le cnt[i]\times val[i]$

其中 $cnt[i]$ 表示第 $i$ 个数的数量，$val[i]$ 表示第 $i$ 个数的值。

那么就是要求一个区间和了。

麻烦在于如果二维转移，时间复杂度还是 $O(n\sum nums)$ 。

这里具体的实现是，先用完全背包计算前缀和，然后最多考虑每个数的次数 $cnt[i]$ 次。

def func():
	dp = [0] * (r + 1)
	dp[0] = 1
	nums_cnt
	// 枚举每个数及其次数
	for v, c in nums_cnt;
		for i in range(x, r + 1):
			dp[i] += dp[i - 1]
		// 这样 dp[i] 就是考虑有 0 个，1 个，... i/v 个数 v 的集合
		// 做完了前缀和
		// 但是需要注意的是，数的数量只有 c 个
		// 所以我们还需要多的部分
		for i in range(r + 1, (c + 1) * v - 1, -1):
			// dp[i] 只能由 dp[i], dp[i-v], dp[i-2v], ..., dp[i-cv] 
			// 转移而来，所以对于 dp[i-(c+1)*v]存储的是 i-(c+1)*v 的前缀和，
			// 其并不能转移到 dp[i] ，删去即可
			dp[i] -= dp[i-(c + 1) * v]
	// 最后考虑 0 选择即可，有 zero + 1 种选法
	return (nums_cnt[0] + 1) * sum(dp[l:r+1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：$O(200\sum nums)$

代码

class Solution {
public:
    int countSubMultisets(vector<int>& nums, int l, int r) {
        const int MAX = 20010;
        const int MOD = 1e9 + 7;
        vector<int> dp(r + 1);
        dp[0] = 1;
        
        vector<int> cnt(MAX);
        vector<int> vec;
        int zero = 0;
        for (int u: nums) {
            if (u == 0) {
                zero += 1;
                continue;
            }
            cnt[u] += 1;
            if (cnt[u] == 1) vec.push_back(u);
        }
        
        for (int u: vec) {
            for (int i = u; i <= r; ++i) {
                dp[i] += dp[i - u];
                if (dp[i] >= MOD) dp[i] -= MOD;
            }
            int left = (cnt[u] + 1) * u;
            for (int i = r; i >= left; --i) {
                dp[i] -= dp[i - left];
                if (dp[i] < 0) dp[i] += MOD;
            }
        }
        
        int ans = 0;
        for (int i = l; i <= r; ++i) {
            ans += dp[i];
            if (ans >= MOD) ans -= MOD;
        }
        
        ans = 1ll * ans * (zero + 1) % MOD;
        
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43