题目内容
原题链接
给定一个长度为
n
n
n 的数组
n
u
m
s
nums
nums 和一个区间左右端点
[
l
,
r
]
[l,r]
[l,r] 。
返回
n
u
m
s
nums
nums 中子多重集合的和在闭区间
[
l
,
r
]
[l, r]
[l,r] 之间的 子多重集合的数目 。
子多重集合 指的是从数组中选出一些元素构成的 无序 集合，每个元素
x
x
x 出现的次数可以是
0
,
1
,
.
.
.
,
o
c
c
[
x
]
0, 1, ..., occ[x]
0,1,...,occ[x] 次，其中
o
c
c
[
x
]
occ[x]
occ[x] 是元素
x
x
x 在数组中的出现次数。
注意：
如果两个子多重集合中的元素排序后一模一样，那么它们两个是相同的子多重集合 。空集合的和是 0 。
数据范围
1
≤
n
≤
2
⋅
1
0
4
1\leq n\leq 2\cdot 10^4
1≤n≤2⋅104
0
≤
n
u
m
s
[
i
]
≤
2
⋅
1
0
4
,
s
u
m
(
n
u
m
s
)
≤
2
⋅
1
0
4
0\leq nums[i]\leq 2\cdot 10^4, sum(nums)\leq 2\cdot 10^4
0≤nums[i]≤2⋅104,sum(nums)≤2⋅104
0
≤
l
≤
r
≤
2
⋅
1
0
4
0\leq l\leq r\leq 2\cdot 10^4
0≤l≤r≤2⋅104
题解
本题从数据范围出发。
考虑
n
u
m
s
nums
nums 总和不超过
20000
20000
20000 ，那么
n
u
m
s
nums
nums 中不同的数有多少个呢？
考虑最小的情况下有
x
x
x 种数，每种数一个，那么总和为：
x
×
(
x
+
1
)
2
\frac{x\times (x+1)}{2}
2x×(x+1)
当
x
=
200
x=200
x=200 时，
x
×
(
x
+
1
)
2
=
20100
>
20000
\frac{x\times (x+1)}{2}=20100>20000
2x×(x+1)=20100>20000 ，故至多有
199
199
199 个不同的数。
那么问题转换为一个分组背包问题，值为
v
v
v 的数的个数有
c
c
c 个，那么可以选择这个数
[
0
,
v
]
[0,v]
[0,v] 次，这样可以转换成
01
01
01 背包，最多有
O
(
n
)
O(n)
O(n) 个物品。
这样时间复杂度为：
O
(
n
∑
n
u
m
s
)
O(n\sum nums)
O(n∑nums) ，
4
e
8
4e8
4e8 不能通过。
考虑从定义出发：
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示前
i
i
i 种物品，容量使用为
j
j
j 的方案数。
那么
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的状态转移方程是什么呢？
d
p
[
i
]
[
j
]
=
∑
k
d
p
[
i
−
1
]
[
k
]
dp[i][j]=\sum\limits_{k} dp[i-1][k]
dp[i][j]=k∑dp[i−1][k] ，满足
0
≤
j
−
k
≤
c
n
t
[
i
]
×
v
a
l
[
i
]
0\leq j-k\leq cnt[i]\times val[i]
0≤j−k≤cnt[i]×val[i]
其中
c
n
t
[
i
]
cnt[i]
cnt[i] 表示第
i
i
i 个数的数量，
v
a
l
[
i
]
val[i]
val[i] 表示第
i
i
i 个数的值。
那么就是要求一个区间和了。
麻烦在于如果二维转移，时间复杂度还是
O
(
n
∑
n
u
m
s
)
O(n\sum nums)
O(n∑nums) 。
这里具体的实现是，先用完全背包计算前缀和，然后最多考虑每个数的次数
c
n
t
[
i
]
cnt[i]
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])
时间复杂度：
O
(
200
∑
n
u
m
s
)
O(200\sum nums)
O(200∑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 l = (cnt[u] + 1) * u;
for (int i = r; i >= l; --i) {
dp[i] -= dp[i - l];
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;
}
};
