蚌埠专业制作网站的公司,五种类型网站,网友,寰宇seo题目内容 原题链接 给定一个长度为 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] 之间的 子多重集合的数目 。
子多重集合 指的是从数组中选出一些元素构成的 …题目内容 原题链接 给定一个长度为 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 (x1)}{2} 2x×(x1) 当 x 200 x200 x200 时 x × ( x 1 ) 2 20100 20000 \frac{x\times (x1)}{2}2010020000 2x×(x1)2010020000 故至多有 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] 1nums_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-(c1)*v]存储的是 i-(c1)*v 的前缀和// 其并不能转移到 dp[i] 删去即可dp[i] - dp[i-(c 1) * v]// 最后考虑 0 选择即可有 zero 1 种选法return (nums_cnt[0] 1) * sum(dp[l:r1])时间复杂度 O ( 200 ∑ n u m s ) O(200\sum nums) O(200∑nums)
代码
class Solution {
public:int countSubMultisets(vectorint nums, int l, int r) {const int MAX 20010;const int MOD 1e9 7;vectorint dp(r 1);dp[0] 1;vectorint cnt(MAX);vectorint 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;}
};
