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

题目

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

---

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

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

由于答案可能很大，请你将答案对 10^9 + 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 <= nums.length <= 2 * 10^4
• 0 <= nums[i] <= 2 * 10^4
• nums 的和不超过 2 * 10^4 。
• 0 <= l <= r <= 2 * 10^4

题解

方法一：

思路

在一些数中选一部分使得和恰好为某个值。由于每个数可以选与不选，我们可以用01背包。

但是这里的对于相同的一个值选取是无差别的，所以如果一个值x重复了k次，选取的方式不是$2^k$次而是$k+1$次。

所以我们可以统计nums中不同数的种数，并统计各个种数出现的次数。然后解决一个多重背包问题。

多重背包的时间复杂度为$O(V\sum m_i)$，$V$为背包总容量，$m_i$为第i个物品出现的次数。

定义$f_{i,j}$为前i件物品，第i物品的选取次数为$m_i$次，体积为$v_i$，在背包容量为j的情况下恰好装满的背包选取方式。

$f_{i,j} = \sum \limits_{k=0}^{m_i} f_{i-1,j-k\cdot v_i}$

代码如下

class Solution {
public:
    int MOD = 1e9+7;
    int countSubMultisets(vector<int>& nums, int l, int r) {
        map<int,int> mp;
        for (auto i:nums) mp[i]++;
        vector<pair<int,int>> a(mp.begin(), mp.end());
        int n = a.size();
        vector<vector<int>> dp(n+1, vector<int>(r+1, 0));
        dp[0][0] = 1;
        for (int i=1; i<=n; i++) {
            auto [x, y] = a[i-1];
            for (int j=0; j<=r; j++) {
                for (int k=0; k<=y; k++) {
                    if (k*x<=j) {
                        dp[i][j] += dp[i-1][j-k*x];
                        dp[i][j] %= MOD;
                    }
                        
                }    
            }
        }
        // for (int i=0; i<=n; i++) {
        //     for (int j=0; j<=r; j++) {
        //         cout << i << " " << j << " = " << dp[i][j] << "\n";
        //     }
        // }
        int ans = 0;
        for (int i=l; i<=r; i++) {
            ans += dp[n][i];
            ans %= MOD;
        }
        return ans;
    }
};

题目$V$最大有2e4，$\sum m_i$为2e4。该代码会超时，需要继续优化。

有一种单调队列优化的多重背包。和完全背包一样，只与物品的种数有关，与每件物品的重复次数无关。使用单调队列是为了能求滑动窗口中的最大值。而本题是背包计数，我们只需要求滑动窗口内的总和即可。

由于nums的和不超过s=2e4，nums中不同的值的个数不会超过$O(\sqrt s)$，所以总时间复杂度为$O(\sqrt s V)$

观察$f_{i,j}$展开

$f_{i,j} = \sum \limits_{k=0}^{m_i} f_{i-1,j-k\cdot v_i}$

$f_{i,j} = f_{i-1, j}+f_{i-1, j-v_i}+\cdots+f_{i-1, j-m_ic_i}$

观察$f_{i,j-v_i}$展开

$f_{i,j-v_i} = \sum \limits_{k=0}^{m_i} f_{i-1,j-(k+1)\cdot v_i}$

$f_{i,j-v_i} = f_{i-1, j-v_i}+f_{i-1, j-2v_i}+\cdots+f_{i-1, j-(m_i+1)c_i}$

$f_{i,j}$和$f_{i, j-v_i}$分别展开后，我们可以认为$f_{i,j}$比$f_{i,j-v_i}$多了$f_{i-1,j}$这一项，少了$f_{i-1, j-(m_i+1)v_i}$这一项。我们可以用滑动窗口来维护。

$f_{i,\dots}$的求解可以分为$v_i$组进行，在$v_i$组中第r组($0\le r < v_i$)为$f_{i-1, r}, f_{i-1, r+v_i}, f_{i-1, r+2v_i}, \cdots, f_{i-1,g\cdot v_i + r}, (g=\lfloor \frac{V}{v_i} \rfloor)$，对这个序列维护一个窗口大小不超过$m_i+1$的滑动窗口。

例如，对于可选次数$m_i$为3，求解$f_{i,4v_i+r} = f_{i-1, 4v_i+r}+f_{i-1,3v_i+r}+f_{i-1, 2v_i+r}+f_{i-1, v_i+r}$

答案要求l到r内的所有值之和，所以答案是$\sum \limits_{i=l}^r f_{n,i}$

注意0需要特殊处理。

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    int countSubMultisets(vector<int>& nums, int l, int r) {
        map<int,int> mp;
        for (int i:nums) mp[i]++;
        vector<pair<int,int>> o;
        for (auto [i,j]:mp) {
            if (i != 0)
                o.emplace_back(i,j);
        }
        int n = o.size(), v = r;
        vector<vector<ll>> f(n+1, vector<ll>(v+1, 0));
        f[0][0] = 1;
        for (int i=1; i<=n; i++) {
            auto [vi, si] = o[i-1];
            // cout << vi << " " << si << endl;
            for (int j=0; j<vi; j++) {
                ll c = 0;
                for (int k=j; k<=v; k+=vi) {
                    c += f[i-1][k];
                    c %= MOD;
                    if (k>si*vi+j) c -= f[i-1][k-(si+1)*vi], c = (c+MOD)%MOD;
                    f[i][k] = c;
                }
            }
        }
        // cout << v << endl;
        // for (int i=0; i<=n; i++) {
        //     for (int j=0; j<=v; j++) {
        //         cout << i << " " << j << " = " << f[i][j] << "\n";
        //     }
        // }
        ll ans = 0;
        for (int i=l; i<=r; i++) {
            ans += f[n][i];
            ans %= MOD;
        }
        return ans*(mp[0]+1)%MOD;
    }
};