|
1 | 1 | packageg2901_3000.s2902_count_of_sub_multisets_with_bounded_sum; |
2 | 2 |
|
3 | 3 | // #Hard #Array #Hash_Table #Dynamic_Programming #Sliding_Window |
4 | | -// #2023_12_26_Time_2146_ms_(5.39%)_Space_70.7_MB_(23.08%) |
| 4 | +// #2023_12_29_Time_17_ms_(100.00%)_Space_45.4_MB_(59.02%) |
5 | 5 |
|
6 | | -importjava.util.ArrayList; |
7 | | -importjava.util.Collections; |
8 | | -importjava.util.HashMap; |
9 | 6 | importjava.util.List; |
10 | 7 |
|
11 | 8 | publicclassSolution { |
12 | | -privatestaticfinalintMOD =(int)1e9 +7; |
13 | | -privateHashMap<Integer,Integer>map; |
14 | | -privateint[][]dp; |
| 9 | +privatestaticfinalintMOD =1000000007; |
| 10 | +privatestaticfinalintMAX =20001; |
| 11 | +privatestaticfinalIntMapINT_MAP =newIntMap(); |
15 | 12 |
|
16 | | -privateintsolve(List<Integer>al,intl,intr,intindex,intsum) { |
17 | | -if (sum >r) { |
| 13 | +publicintcountSubMultisets(List<Integer>nums,intl,intr) { |
| 14 | +INT_MAP.clear(); |
| 15 | +INT_MAP.add(0); |
| 16 | +inttotal =0; |
| 17 | +for (intnum :nums) { |
| 18 | +INT_MAP.add(num); |
| 19 | +total +=num; |
| 20 | + } |
| 21 | +if (total <l) { |
18 | 22 | return0; |
19 | 23 | } |
20 | | -longans =0; |
21 | | -if (index >=al.size()) { |
22 | | -return (int)ans; |
| 24 | +r =Math.min(r,total); |
| 25 | +finalint[]cnt =newint[r +1]; |
| 26 | +cnt[0] =INT_MAP.map[0]; |
| 27 | +intsum =0; |
| 28 | +for (inti =1;i <INT_MAP.size;i++) { |
| 29 | +finalintval =INT_MAP.vals[i]; |
| 30 | +finalintcount =INT_MAP.map[val]; |
| 31 | +if (count >0) { |
| 32 | +sum =Math.min(r,sum +val *count); |
| 33 | +update(cnt,val,count,sum); |
| 34 | + } |
23 | 35 | } |
24 | | -if (dp[index][sum] != -1) { |
25 | | -returndp[index][sum]; |
| 36 | +intres =0; |
| 37 | +for (inti =l;i <=r;i++) { |
| 38 | +res = (res +cnt[i]) %MOD; |
26 | 39 | } |
27 | | -intcur =al.get(index); |
28 | | -intcount =map.get(cur); |
29 | | -for (inti =0;i <=count;i++) { |
30 | | -intcurSum =sum +cur *i; |
31 | | -if (curSum >r) { |
32 | | -break; |
| 40 | +returnres; |
| 41 | + } |
| 42 | + |
| 43 | +privatestaticvoidupdate(finalint[]cnt,finalintn,finalintcount,finalintsum) { |
| 44 | +if (count ==1) { |
| 45 | +for (inti =sum;i >=n;i--) { |
| 46 | +cnt[i] = (cnt[i] +cnt[i -n]) %MOD; |
33 | 47 | } |
34 | | -ans =ans +solve(al,l,r,index +1,curSum); |
35 | | -if (i !=0 &&curSum >=l) { |
36 | | -ans =ans +1; |
| 48 | + }else { |
| 49 | +for (inti =n;i <=sum;i++) { |
| 50 | +cnt[i] = (cnt[i] +cnt[i -n]) %MOD; |
| 51 | + } |
| 52 | +finalintmax = (count +1) *n; |
| 53 | +for (inti =sum;i >=max;i--) { |
| 54 | +cnt[i] = (cnt[i] -cnt[i -max] +MOD) %MOD; |
37 | 55 | } |
38 | | -ans =ans %MOD; |
39 | 56 | } |
40 | | -dp[index][sum] = (int)ans; |
41 | | -return (int)ans; |
42 | 57 | } |
43 | 58 |
|
44 | | -publicintcountSubMultisets(List<Integer>nums,intl,intr) { |
45 | | -map =newHashMap<>(); |
46 | | -List<Integer>al=newArrayList<>(); |
47 | | -for (intcur :nums) { |
48 | | -intcount =map.getOrDefault(cur,0) +1; |
49 | | -map.put(cur,count); |
50 | | -if (count ==1) { |
51 | | -al.add(cur); |
| 59 | +privatestaticfinalclassIntMap { |
| 60 | +finalint[]map =newint[MAX]; |
| 61 | +finalint[]vals=newint[MAX]; |
| 62 | +intsize =0; |
| 63 | + |
| 64 | +voidadd(intv) { |
| 65 | +if (map[v]++ ==0) { |
| 66 | +vals[size++] =v; |
52 | 67 | } |
53 | 68 | } |
54 | | -intn =al.size(); |
55 | | -dp =newint[n][r +1]; |
56 | | -for (inti =0;i <dp.length;i++) { |
57 | | -for (intj =0;j <dp[0].length;j++) { |
58 | | -dp[i][j] = -1; |
| 69 | + |
| 70 | +voidclear() { |
| 71 | +for (inti =0;i <size;i++) { |
| 72 | +map[vals[i]] =0; |
59 | 73 | } |
| 74 | +size =0; |
60 | 75 | } |
61 | | -Collections.sort(al); |
62 | | -intans =solve(al,l,r,0,0); |
63 | | -if (l ==0) { |
64 | | -ans =ans +1; |
65 | | - } |
66 | | -ans =ans %MOD; |
67 | | -returnans; |
68 | 76 | } |
69 | 77 | } |