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

发表于 分类于 阅读次数： Waline： 本文字数： 568 阅读时长 ≈ 2 分钟

考点

  • 多重背包
  • 前缀和
  • 乘法原理
  • 滑动窗口

思路

先把0的情况剥开，最后再考虑0

道理很简单，假设有2个0，对于集合{1, 3}而言，可以变成{1, 3}、{0, 1, 3}、{0, 0, 1, 3}三种

所以假设0有cnt个，对于任何一个集合，它都能给予额外的cnt + 1倍

有两种处理方法：

  1. 最后乘上cnt + 1
  2. 直接令f[0][0] = cnt[0] + 1;即可

举个例子：

1
2
nums = [0, 0, 2]
z = 2

只考虑 0 和一个权值为 2、数量为 1 的物品。

第一种写法：

  • 初始：f[0] = 1
  • 加入一个 2（只一件）：
    • 和 0：不选 2 → 1 种
    • 和 2：选 2 → 1 种 所以 g[0] = 1, g[2] = 1
  • 最后考虑 0：
    • 每种方案都可以配 0/1/2 个 0，一共 3 倍 所以真正的：
    • g[0] = 3 * 1 = 3
    • g[2] = 3 * 1 = 3

第二种写法：

  • 初始就考虑 0：f[0] = cnt + 1 = 3
  • 加入一个 2：
    • 和 0：不选 2 → 3 种（只选 0 的方式）
    • 和 2：在「和 0」的 3 种基础上选 2 → 3 种 所以直接得到：
    • g[0] = 3
    • g[2] = 3

然后滑动窗口的解法：

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
class Solution {
 public:
  static const int maxn = 2e4 + 5, mod = 1e9 + 7;
  int countSubMultisets(vector<int>& nums, int l, int r) {
    unordered_map<int, int> cnt;
    for (int& x : nums) cnt[x]++;
    int f[2][maxn], n = 0;
    memset(f, 0, sizeof(f));
    f[0][0] = cnt[0] + 1;
    int m = 0;
    for (auto& it : cnt) {
      int w = it.first, c = it.second;
      if (!w) continue;
      m = min(r, m + w * c);
      for (int r = 0; r < w; ++r) {
        long long sum = 0;
        for (int j = r, k = 0; j <= m; j += w, k++) {
          sum = (sum + f[n & 1][j]) % mod;
          if (k - (c + 1) >= 0)
            sum = (sum - f[n & 1][r + (k - c - 1) * w] + mod) % mod;
          f[n + 1 & 1][j] = sum;
        }
      }
      n++;
    }
    long long ans = 0;
    for (int i = l; i <= r; ++i) ans = (ans + f[n & 1][i]) % 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
class Solution {
 public:
  static const int maxn = 2e4 + 5, mod = 1e9 + 7;
  int countSubMultisets(vector<int>& nums, int l, int r) {
    unordered_map<int, int> cnt;
    for (int& x : nums) cnt[x]++;
    long long f[maxn];
    int m = 0;
    memset(f, 0, sizeof(f));
    f[0] = cnt[0] + 1;
    for (auto& it : cnt) {
      int w = it.first, c = it.second;
      if (!w) continue;
      m = min(r, m + w * c);
      for (int j = w; j <= m; ++j) f[j] = (f[j] + f[j - w]) % mod;
      for (int j = m; j >= (c + 1) * w; --j) {
        f[j] = (f[j] - f[j - (c + 1) * w] + mod) % mod;
      }
    }
    long long ans = 0;
    for (int i = l; i <= r; ++i) ans = (ans + f[i]) % mod;
    return ans;
  }
};