Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.5k 阅读时长 ≈ 2 分钟
多重背包，但是需要优化。

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

题目描述：

给你一个下标从 0 开始的非负整数数组 nums 和两个整数 l 和 r 。

请你返回 nums 中子多重集合的和在闭区间 [l, r] 之间的 子多重集合的数目 。

由于答案可能很大，请你将答案对 $10^9 + 7$ 取余后返回。

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

注意：

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

数据范围：

$1\le nums.len \le 2 \times 10^4; 0\le l \le r \le 2\times 10^4$

题解：

多重背包求方案数，枚举每种元素取得个数。

该问题可以设 $dp[i][j]$ 为不超过容量 $j$ 的方案数，然后 $dp[n][r] - dp[n][l - 1]$ 。也可以求恰好的，然后 $\sum_{v = l}^rdp[n][v]$ 。二者的区别就在于初始化，不超过需要初始化 $dp[0][0,\cdots,r] = 1$ ，恰好需要初始化 $dp[0][0] = 1$ 。

假设 $dp[i][j]$ 表示前 $i$ 种元素，恰好装满背包 $j$ 有多少种方案。则对于第 $i$ 种，枚举选的个数。

但是复杂度比较高，复杂度大约为 $O(r \times n) \approx 4\times10^8$ ，会超时。

方法一，展开公式求解：

展开递推式：

因为每一个都要枚举 $k + 1$ 次，所以项数是一样的。

一般的有：

需要多减去一项。

如果 $j - (cnt[v] + 1)v < 0$ 则：

实际上就是一个窗口大小为 $[j - kv, j]$ 的滑动窗口，其实就是长度为 $cnt[v] + 1$ 。而且每种余数 $j\%v$ 都有一个滑动窗口，求滑动窗口内部的累加值，滑动时，每次加一个尾部的数字，减去头部数字。

需要注意的是， $dp[i][j]$ 在 $[0, v)$ 还有一段。

另外一个需要注意的地方就是 $0$ 需要单独计算贡献。因为不同数量的 $0$ 在dp数组中都是同一个格子，会被重复计算。首先计算出来不包含 $0$ 的方案数，然后用 $cnt[0] + 1$ 乘以该答案。

方法二，前缀和优化：

代码：

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
44
45
46
47
48
49
50
51
52
53
54
55
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const long long mod = 1e9 + 7;
    int countSubMultisets(vector<int> &nums, int l, int r)
    {
        vector<pair<int, int>> a;
        unordered_map<int, int> mp;
        for (auto &x : nums)
        {
            mp[x]++;
        }
        int cnt0 = 0;
        for (auto &[key, value] : mp)
        {
            if (key == 0)
                cnt0 = value;
            else
                a.emplace_back(key, value);
        }
        int n = a.size();
        long long ans = 0;
        vector<vector<int>> dp(n + 1, vector<int>(r + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= r; ++j)
            {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
                if (j - a[i - 1].first >= 0)
                    dp[i][j] = (dp[i][j] + dp[i][j - a[i - 1].first]) % mod;
                if (j - (a[i - 1].second + 1) * a[i - 1].first >= 0)
                {
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - (a[i - 1].second + 1) * a[i - 1].first] + mod) % mod;
                }
            }
        }
        for (int i = l; i <= r; ++i)
        {
            ans = (ans + dp[n][i]) % mod;
        }
        ans = (cnt0 + 1) * ans % mod;
        return ans;
    }
};