和带限制的子多重集合的数目-526互联

给你一个下标从 0 开始的非负整数数组 nums 和两个整数 l 和 r 。
请你返回 nums 中子多重集合的和在闭区间 [l, r] 之间的子多重集合的数目。

1. 多重背包 + 滑动窗口

class Solution {
public:
    int countSubMultisets(vector<int> &nums, int l, int r) {
        const int MOD = 1e9 + 7;
        int total = 0;
        unordered_map<int, int> cnt;//统计每个物品的个数
        for (int x: nums) {
            total += x;
            cnt[x]++;
        }
        if (l > total) return 0;

        r = min(r, total);
        vector<int> f(r + 1);//记录f[i]恰为i的组合个数，求组合数的背包问题，枚举物品，再枚举范围
        f[0] = cnt[0] + 1;//边界初始状态，重要
        cnt.erase(0);

        int sum = 0;//当前的枚举范围
        for (auto [x, c]: cnt) {//枚举物品
            auto new_f = f;//复制当前数组，用于滑动变量减少内存
            sum = min(sum + x * c, r); //减少枚举上界范围，优化
            for (int j = x; j <= sum; j++) {//
                new_f[j] = (new_f[j] + new_f[j - x]) % MOD;
                if (j >= (c + 1) * x)//大于这个范围的，会重复使用超过c次该物品
                    new_f[j] = (new_f[j] - f[j - (c + 1) * x] + MOD) % MOD; //滑动窗口
            }
            f = move(new_f);
        }

        int ans = 0;
        for (int i = l; i <= r; i++) 
            ans = (ans + f[i]) % MOD;
        return ans;
    }
};

1. 多重背包 + 二进制优化