3428. Maximum and Minimum Sums of at Most Size K Subsequences

Posted on Edited on In

3428. Maximum and Minimum Sums of at Most Size K Subsequences

Description

You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subsequences of nums with at most k elements.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

1
2
3
Input: nums = [1,2,3], k = 2

Output: 24

Explanation:

The subsequences of nums with at most 2 elements are:

Subsequence MinimumMaximumSum
[1]112
[2]224
[3]336
[1, 2]123
[1, 3]134
[2, 3]235
Final Total24

The output would be 24.

Example 2:

Input: nums = [5,0,6], k = 1

Output: 22

Explanation:

For subsequences with exactly 1 element, the minimum and maximum values are the element itself. Therefore, the total is 5 + 5 + 0 + 0 + 6 + 6 = 22.

Example 3:

Input: nums = [1,1,1], k = 2

Output: 12

Explanation:

The subsequences [1, 1] and [1] each appear 3 times. For all of them, the minimum and maximum are both 1. Thus, the total is 12.

Constraints:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= min(70, nums.length)

Hints/Notes

Solution

Language: C++

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public:
    const int MOD = 1e9 + 7;
    vector<int> fac, inv;
    int n;

    void init() {
        for (int i = 1; i < n; i++) {
            fac[i] = (long)fac[i - 1] * i % MOD;
        }
        // now to calculate inv(逆元)
        // 费马小定理：(a / b) mod p = a * b ^(p - 2) mod p (when p is a prime number)
        inv[n - 1] = qpow(fac[n - 1], MOD - 2);
        // now we get the inv of fac[n], to get inv of fac[n - 1]
        // fac[n - 1] = fac[n] / n
        // fac[n] * inv[n] = 1 mod p
        // fac[n - 1] * n * inv[n] = 1 mod p
        // n * inv[n] is inv[n - 1]
        for (int i = n - 2; i >= 1; i--) {
            inv[i] = (long)inv[i + 1] * (i + 1) % MOD;
        }
    }

    int qpow(int b, int n) {
        int res = 1;
        while (n) {
            if (n % 2) {
                res = (long)res * b % MOD;
            }
            b = (long)b * b % MOD;
            n >>= 1;
        }
        return res;
    }

    int minMaxSums(vector<int>& nums, int k) {
        n = nums.size();
        fac.resize(n, 1);
        inv.resize(n, 1);
        init();
        // look at each number, how many times it's taken as smallest number
        // and how many times it's taken as maximum number
        // sort first
        // for nums[0], it's taken as smallest number in
        // k = 1, with C(n - 1, 0)
        // k = 2, with C(n - 1, 1)
        // k = 3, with C(n - 1, 2)
        // k = 4, with C(n - 1, 3)
        // ...
        // k = k, with C(n - 1, k - 1)
        // for nums[1], it's taken as smallest number in
        // k = 1, with C(n - 2, 0),
        // k = 2, with C(n - 2, 1),
        // ...
        // k = k, with C(n - 2, k - 1)
        // for one number, how many times does it been taken as maximum number?
        // it's the same as maximum number
        long res = 0;
        ranges::sort(nums);
        for (int i = 0; i < n; i++) {
            // n - 1 - i - j >= 0, j <= n - 1 - i => j < n - i
            for (int j = 0; j < min(k, n - i); j++) {
                res = (res + (long)fac[n - 1 - i] * inv[j] % MOD * inv[n - 1 - i - j] % MOD * nums[i] % MOD) % MOD;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < min(k, i + 1); j++) {
                res = (res + (long)fac[i] * inv[j] % MOD * inv[i - j] % MOD * nums[i] % MOD) % MOD;
            }
        }
        return res;
    }
};